Máquina de estado no determinista

Un autómata finito no determinista (NFA, ing. nondeterministic finite automaton , NFA) es un autómata finito determinista (DFA, ing. deterministic finite automaton , DFA) que no cumple las siguientes condiciones:

cualquiera de sus transiciones está determinada únicamente por el estado actual y el símbolo de entrada
se requiere leer un carácter de entrada para cada cambio de estado.

En particular, cualquier DFA es también un NFA.

Usando el algoritmo de construcción de subconjuntos , cualquier NFA se puede convertir en un DFA equivalente, es decir, un DFA que reconoce el mismo lenguaje formal [1] . Al igual que DFA, NFA solo reconoce lenguajes regulares .

NFA fue propuesto en 1959 por Michael O. Rabin y Dana Scott [2] quienes demostraron que era equivalente a DFA. NFA se usa en la implementación de expresiones regulares : la construcción de Thompson es un algoritmo para convertir una expresión regular en NFA que puede reconocer de manera eficiente el patrón de cadenas. Por el contrario, el algoritmo de Kleene se puede utilizar para transformar un NFA en una expresión regular cuyo tamaño en general depende exponencialmente del tamaño del autómata.

NFA se generaliza de muchas maneras, por ejemplo: autómatas finitos no deterministas con transiciones ε , transductores de estado finito, autómatas pushdown, autómatas alternos, autómatas ω y autómatas probabilísticos . Además de DFA, se conocen otros casos especiales de NFA: autómatas finitos no ambiguos ( ing. autómatas finitos unambiguos , UFA) y autómatas finitos autoverificadores ( ing. autómatas finitos autoverificadores , SVFA).

Introducción informal

Hay varias descripciones informales equivalentes:

Un NFA, como un DFA , toma una cadena de caracteres de entrada. Para cada símbolo de entrada, pasa a un nuevo estado hasta que haya procesado todos los símbolos de entrada. En cada paso, el autómata elige aleatoriamente una de las posibles transiciones. Si hay un "paso esperanzado", es decir, alguna secuencia de opciones que conducen a un estado final después de que la cadena de entrada se haya obtenido por completo, entonces se acepta la cadena. Si no hay una secuencia que, después de procesar toda la cadena de entrada [3] , lleve el autómata al estado final, entonces la cadena de entrada se rechaza [4] [5] .
Deje que NFA vuelva a tomar una cadena de caracteres de entrada, un carácter tras otro. En cada paso en el que dos o más transiciones resultan válidas, el autómata se "clona" a sí mismo en el número requerido de copias, cada una de las cuales realiza transiciones diferentes. Si no se puede realizar ninguna transición, la copia actual es un callejón sin salida y muere. Si, después de obtener todos los caracteres de la cadena de entrada, alguna de las copias pasa al estado final, se acepta la cadena de entrada; de lo contrario, se rechaza [6] [7] [8] .

Formal definición

Para una introducción más elemental a la definición formal, ver el artículo " Teoría de Autómatas ".

Autómatas

Un NFA se representa formalmente como una tupla de 5 que consta de: ${\ estilo de visualización (Q, \ Sigma, \ Delta, q_{0}, F)}$

conjunto finito de estados . $q$
conjunto finito de símbolos de entrada . $\Sigma$
funciones de transición : . $\Delta$ $Q\veces\Sigma\rightarrow P(Q)$
estado inicial . $q_{0}\en Q$
conjuntos de estados reconocibles como estados finales . $F$ $F\subconjunto Q$

Aquí significa el grado del conjunto . ${\ estilo de visualización P (Q)}$ $q$

Idioma reconocido

Dado un NFA , reconoce un idioma que se denota y define como el conjunto de todas las cadenas sobre el alfabeto aceptado por el autómata . $M=(Q,\Sigma,\Delta,q_{0},F)$ ${\ estilo de visualización L (M)}$ $\Sigma$ $METRO$

En términos generales, de acuerdo con las explicaciones informales anteriores , existen varias definiciones de cadenas formales equivalentes aceptadas por el autómata : ${\displaystyle w=a_{1}a_{2}...a_{n))$ $METRO$

$w$ se acepta si hay una secuencia de estados tal que ${\displaystyle r_{0},r_{1},...,r_{n))$ $q$
1. $r_{0}=q_{0}$
2. $r_{i+1}\in\Delta (r_{i},a_{i+1})$ , por $i=0,\ldots,n-1$
3. ${\ Displaystyle r_ {n} \ en F}$ .

Palabras. La primera condición dice que la máquina parte del estado . La segunda condición dice que para cada carácter de la cadena , la máquina pasa de un estado a otro según la función de transición . La última condición dice que la máquina acepta una cadena si la cadena de entrada hace que la máquina termine en su estado final. Para que una cadena sea aceptada por un autómata , no se requiere que ninguna secuencia de estados termine en un estado final, es suficiente que una secuencia conduzca a tal estado. De lo contrario, es decir , si es imposible pasar del estado de , siguiendo a , se dice que el autómata rechaza la cadena. El conjunto de cadenas que acepta el autómata es un lenguaje reconocido por el autómata , y este lenguaje se denota como [9] [10] .

q_{0}

w

\Delta

w

w

w

METRO

q_{0}

F

w

METRO

METRO

{\ estilo de visualización L (M)}

Alternativamente, se acepta si , donde se determina recursivamente : $w$ $\Delta ^{*}(q_{0},w)\cap F\not =\emptyset$ ${\displaystyle\Delta ^{*}:Q\times\Sigma ^{*}\rightarrow P(Q)}$
1. ${\displaystyle \Delta ^{*}(r,\epsilon)=\{r\))$ , donde esta la cadena vacia $\epsilon$
2. $\Delta ^{*}(r,xa)=\bigcup _{r'\in \Delta ^{*}(r,x)}\Delta (r',a)$ para cualquier $x\en \Sigma ^{*},a\en \Sigma$

En otras palabras, es el conjunto de todos los estados accesibles desde el estado al obtener la cadena . Se acepta una cadena si se puede alcanzar algún estado final desde el estado inicial para la cadena de entrada [11] [12] .

{\ estilo de visualización \ Delta ^ {*} (r, x)}

r

X

w

F

q_{0}

w

Estado inicial

La definición de autómata anterior utiliza un solo estado inicial , que no es un requisito. A veces, una NFA se define con un conjunto de estados iniciales. Hay una construcción simple que lleva un NFA con múltiples estados iniciales a un NFA con un solo estado inicial.

Ejemplo

El siguiente autómata del alfabeto binario determina si la cadena de entrada termina en uno. Sea , donde la función de transición se puede definir mediante la siguiente tabla de transición de estado (compárese con la figura superior a la izquierda): $METRO$ $M=(\{p,q\},\{0,1\},\Delta,p,\{q\})$ $\Delta$

EntradaEstado	0	una
$pags$	${\ estilo de visualización \ {p \}}$	${\ estilo de visualización \ {p, q \}}$
$q$	$\conjunto vacio$	$\conjunto vacio$

Dado que el conjunto contiene más de un estado, el autómata no es determinista. El lenguaje autómata se puede describir como un lenguaje regular dado por una expresión regular . ${\ estilo de visualización \ Delta (p, 1)}$ $METRO$ $METRO$ (0|1)*1

Todas las posibles secuencias de estado para la cadena de entrada "1011" se muestran en la siguiente figura. El autómata acepta la cadena porque una de las secuencias de estado satisface la definición anterior. No importa que las otras secuencias no tengan éxito. El dibujo se puede interpretar de dos maneras: $METRO$

En términos de la explicación de la "carrera de la suerte" anterior , cada camino en la figura representa una secuencia de opciones . $METRO$
Para explicar en términos de "clonación", cada columna vertical muestra todos los clones del autómata en un momento dado, varias flechas saliendo de un nodo significa clonación, un nodo sin flechas salientes significa "muerte" del clon. $METRO$

La capacidad de leer la misma figura de dos maneras también muestra la equivalencia de las dos explicaciones anteriores.

Si consideramos la primera de las definiciones formales anteriores , se acepta la cadena "1011", porque cuando se lee , puede pasar una secuencia de estados que satisface las condiciones 1-3. $METRO$ $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$
Si consideramos la segunda de las definiciones formales, el pasaje de abajo hacia arriba muestra que , luego , y luego , de dónde , y, finalmente, . Dado que este conjunto contiene , se acepta la cadena "1011". $\Delta ^{*}(p,\epsilon)=\{p\}$ ${\displaystyle \Delta ^{*}(p,1)=\Delta (p,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(p,10)=\Delta (p,0)\taza \Delta (q,0)=\{p\}\taza \{\))$ ${\displaystyle \Delta ^{*}(p,101)=\Delta (p,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(p,1011)=\Delta (p,1)\taza \Delta (q,1)=\{p,q\}\taza \{\))$ ${\ estilo de visualización \ {q \}}$

Por el contrario, la cadena "10" es rechazada por el autómata (todas las posibles secuencias de estados de la cadena de entrada para una entrada dada se muestran en la figura superior derecha), ya que no hay un camino que llegue al estado final después de leer el final . carácter 0. Aunque se puede alcanzar el estado después de recibir el primer carácter "1" no significa que la cadena de entrada "10" sea aceptable. Solo significa que la cadena de entrada "1" sería aceptable. $METRO$ $q$ $q$

Equivalencia DFA

Un autómata finito determinista ( DFA ) puede considerarse como un tipo especial de NFA en el que para cualquier estado y letras del alfabeto, la función de transición tiene solo un estado resultante. Por lo tanto, está claro que cualquier lenguaje formal que pueda reconocerse con un DFA también puede reconocerse con un NFA.

Por el contrario, para cualquier NFA hay un DFA que reconoce el mismo lenguaje formal. Un DFA se puede construir utilizando la construcción de subconjuntos .

Este resultado muestra que el NFA, a pesar de su gran flexibilidad, es incapaz de reconocer lenguajes que ningún DFA puede reconocer. Esto también es importante en la práctica para convertir NFA estructuralmente más simples en DFA computacionalmente más eficientes. Sin embargo, si la NFA tiene n estados, la DFA resultante puede tener hasta 2n estados, lo que a veces hace que la construcción no sea práctica para NFA grandes.

NCA con transiciones ε

El autómata finito no determinista con transiciones ε (NFA-ε) ya es una generalización adicional para NFA. Este autómata de función de transición puede tener la cadena vacía ε como entrada. Una transición sin usar un símbolo de entrada se llama transición ε. En un diagrama de estado, estas transiciones generalmente se etiquetan con la letra griega ε. Las transiciones ε proporcionan una manera conveniente de modelar sistemas cuyo estado actual no se conoce con exactitud. Por ejemplo, si estamos modelando un sistema cuyo estado actual no está claro (después de procesar alguna cadena de entrada) y puede ser q o q', podemos agregar una transición ε entre estos dos estados, llevando el autómata a ambos estados en al mismo tiempo.

Formal definición

NFA-ε se representa formalmente por una tupla de 5 , que consta de: ${\ estilo de visualización (Q, \ Sigma, \ Delta, q_{0}, F)}$

conjunto finito de estados $q$
un conjunto finito de caracteres de entrada , llamado alfabeto $\Sigma$
funciones de transición $\Delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow P(Q)$
estado inicial (o de inicio ) $q_{0}\en Q$
un conjunto de estados que se consideran estados válidos (o finales ) . $F$ $F\subconjunto Q$

Aquí significa la potencia del conjunto , y ε significa la cadena vacía. ${\ estilo de visualización P (Q)}$ $q$

ε-Cierre de un estado o conjunto de estados

Para un estado, denotemos el conjunto de estados alcanzables a partir de las siguientes transiciones ε en las funciones de transición , es decir, si hay una secuencia de estados tal que: ${\ estilo de visualización q \ en Q}$ ${\ estilo de visualización E (q)}$ $q$ $\Delta$ $p\in E(q)$ ${\ Displaystyle q_ {1},..., q_ {k}}$

${\ estilo de visualización q_ {1} = q}$ ,
$q_{i+1}\in \Delta (q_{i},\epsilon)$ para cualquier $1\leqslant i<k$
${\ estilo de visualización q_ {k} = p}$ .

El conjunto se conoce como cierre de estado ε . ${\ estilo de visualización E (q)}$ $q$

El cierre ε también se define para el conjunto de estados. El cierre ε del conjunto de estados, , del autómata NK se define como el conjunto de estados que se pueden alcanzar a partir de los elementos del conjunto mediante transiciones ε. Formalmente, por $PAGS$ $PAGS$ $P\subseteq QE(P)=\cup _{q\in P}E(q)$

Estados aceptables

Sea una cadena sobre el alfabeto . El autómata acepta una cadena si hay una secuencia de estados con las siguientes condiciones: ${\displaystyle w=a_{1}a_{2}...a_{n))$ $\Sigma$ $METRO$ $w$ ${\displaystyle r_{0},r_{1},...,r_{n))$ $q$

$r_{0}\en E(q_{0})$
$r_{i+1}\en E(r')$ , donde para cualquier $r'\in \Delta (r_{i},a_{i+1})$ ${\ estilo de visualización i = 0,..., n-1}$
${\ Displaystyle r_ {n} \ en F}$ .

Palabras. La primera condición dice que la máquina parte de un estado al que se puede acceder desde el estado a través de transiciones ε. La segunda condición dice que después de leer , la máquina selecciona la transición de a y luego realiza cualquier número de transiciones ε según la transición de a . La última condición dice que la máquina acepta si el último carácter ingresado hace que la máquina pase a uno de los estados aceptados. De lo contrario, se dice que el autómata rechaza la cadena. El conjunto de cadenas que acepta es el idioma que reconoce el autómata , y este idioma se denota como .

q_{0}

ai}

\Delta

Rhode Island}

r'

\Delta

r'

r_{i+1}

w

METRO

METRO

{\ estilo de visualización L (M)}

Ejemplo

Sea un NFA-ε con un alfabeto binario que determine si la cadena de entrada contiene un número par de ceros o un número par de unos. Tenga en cuenta que 0 ocurrencias es un número par. $METRO$

En notación formal, sea , donde la relación de transición puede definirse mediante una tabla de transición de estado : $M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\Delta,S_{0} ,\{S_{1},S_{3}\})$ $\Delta$

EntradaEstado	0	una	ε
S0 _	{}	{}	{ S 1 , S 3 }
S1 _	{ S2 } _	{ S 1 }	{}
S2 _	{ S 1 }	{ S2 } _	{}
S3 _	{ S 3 }	{ S4 } _	{}
S4 _	{ S4 } _	{ S 3 }	{}

$METRO$ puede pensarse como la unión de dos DFA , uno con estados y el otro con estados . El lenguaje se puede describir como un lenguaje regular dado por la expresión regular (1*(01*01*)*) ∪ (0*(10*10*)*). Definimos usando transiciones ε, pero podemos definir sin ellas. ${\ estilo de visualización \ {S_ {1}, S_ {2} \}}$ ${\ estilo de visualización \ {S_ {3}, S_ {4}\}}$ $METRO$ $METRO$ $METRO$

Equivalencia de NFAs

Para mostrar que NFA-ε es equivalente a NFA, primero tenga en cuenta que NFA es un caso especial de NFA-ε, queda por mostrar que para cualquier NFA-ε hay un NFA equivalente.

Sea NFA-ε. NFA es equivalente a , donde para cualquiera y . $A=(Q,\Sigma,\Delta,q_{0},F)$ $A'=(Q,\Sigma ,\Delta ',E(q_{0}),F)$ $A$ ${\ estilo de visualización \ en \ Sigma}$ ${\ estilo de visualización q \ en Q}$ $\Delta '(q,a)=E(\Delta (q,a))$

Entonces NFA-ε es equivalente a NFA. Dado que NFA es equivalente a DFA, NFA-ε también es equivalente a DFA.

Propiedades de cierre

Se dice que un NFA está cerrado bajo una operación ( binaria / unaria ). Si la NFA reconoce los idiomas que se obtienen aplicando esta operación a los idiomas reconocidos por la NFA. Las NFA están cerradas con respecto a las siguientes operaciones.

Fusión (ver imagen)
intersección
Concatenación
Suma
Cierre Kleene

Dado que los NFA son equivalentes a los autómatas finitos no deterministas de transición ε (NFA-ε), los cierres anteriores se prueban utilizando las propiedades de cierre de NFA-ε. De las propiedades de cierre anteriores se deduce que los NFA solo reconocen lenguajes regulares .

Los NFA se pueden construir a partir de cualquier expresión regular usando el algoritmo de Thompson .

Propiedades

La máquina parte de un determinado estado inicial y lee una cadena de caracteres compuesta por las letras de su alfabeto . El autómata utiliza la función de transición Δ para determinar el siguiente estado desde el estado actual y el carácter o cadena vacía que acaba de leer. Sin embargo, “el siguiente estado de la NFA depende no solo del símbolo de entrada actual, sino también de un número arbitrario de eventos de entrada posteriores. Mientras tienen lugar estos eventos posteriores, es imposible determinar en qué estado se encuentra la máquina” [13] . Si el autómata está en el estado final después del último carácter leído, se dice que la NFA acepta la cadena; de lo contrario, se dice que la rechaza.

El conjunto de todas las cadenas aceptadas por la NFA es el idioma que acepta la NFA. Este lenguaje es un lenguaje regular .

Para cualquier NFA, se puede encontrar un autómata finito determinista (DFA) que acepte el mismo lenguaje. Por lo tanto, es posible convertir un NFA existente en un DFA para implementar una máquina (posiblemente) más simple. Tal transformación se lleva a cabo utilizando la construcción de subconjuntos , que puede conducir a un aumento exponencial en el número de estados requeridos. Para una prueba formal de la construcción del subconjunto, consulte el artículo " Construcción del subconjunto ".

Implementación

NFA se puede modelar de una de las siguientes maneras:

Convertir a DFA equivalente. En algunos casos, esto puede llevar a un crecimiento explosivo en el número de estados [14] .
Manteniendo el conjunto de todos los estados en los que se puede encontrar el NFA después de la lectura de la palabra. Al procesar un símbolo de entrada, es necesario combinar los resultados de la función de transición aplicada al conjunto de estados actual para obtener el siguiente conjunto. Si se permiten las transiciones ε, también se deben incluir todos los estados alcanzables a través de tales transiciones (cierre ε). Cada paso requiere como máximo cálculos, donde s es el número de estados NFA. El autómata acepta una cadena si y solo si, al procesar el último carácter de entrada, uno de los estados actuales es final. Una cadena de longitud n se puede procesar en tiempo O (ns 2 ) [15] usando memoria O ( s ). $^{2}$

Aplicaciones NCA

NFA y DFA son equivalentes en el sentido de que si un lenguaje es reconocido por un NFA por un autómata, también lo es por un DFA. Lo contrario también es cierto. Establecer tal equivalencia es importante y útil. Importante porque los NFA se pueden usar para reducir la complejidad del trabajo matemático que se necesita para establecer propiedades importantes en la teoría de algoritmos . Por ejemplo, es mucho más fácil probar la clausura de los lenguajes regulares con NFA que con DFA. Útil porque construir un NFA para reconocer ese idioma a veces es mucho más importante que construir un DFA para ese idioma.

Véase también

Máquina de estado determinista
Máquina finita no determinista bidireccional
Automático con memoria de cargador
máquina de Turing

Notas

↑ Martín, 2010 , pág. 108.
↑ Rabin y Scott, 1959 , pág. 114–125.
↑ Una secuencia de elección puede conducir a un "callejón sin salida" en el que ninguna de las transiciones es válida para el símbolo de entrada actual, y este caso se considera un error (se rechaza la cadena).
↑ Hopcroft, Ullman, 1979 , pág. 19
↑ Aho, Hopcroft y Ullman 1974 , pág. 319.
↑ Hopcroft, Ullman, 1979 , pág. 19-20.
↑ Sipser, 1997 , pág. 48.
↑ Hopcroft, Motwani, Ullman, 2001 , pág. 56.
↑ Aho, Hopcroft y Ullman 1974 , pág. 320.
↑ Sipser, 1997 , pág. 54.
↑ Hopcroft, Ullman, 1979 , pág. 21
↑ Hopcroft, Motwani, Ullman, 2001 , pág. 59.
↑ Máquina de estados finitos FOLDOC Diccionario gratuito en línea de computación . Fecha de acceso: 11 de febrero de 2020. Archivado desde el original el 4 de abril de 2015. (indefinido)
↑ Chris Calabro. Explosión de NFA a DFA. 2005-02-27 . Consultado el 11 de febrero de 2020. Archivado desde el original el 7 de febrero de 2013. (indefinido)
↑ Hopcroft, Motwani, Ullman, 2001 , pág. 153.

Literatura

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. El Diseño y Análisis de Algoritmos Informáticos . - Lectura/MA: Addison-Wesley, 1974. - ISBN 0-201-00029-6 .
- Aho A., Hopcroft J., Ulman J. Construcción y análisis de algoritmos computacionales. - Moscú: Mir, 1979.
John E. Hopcroft, Jeffrey D. Ullman. Introducción a la teoría de autómatas, lenguajes y computación . - Lectura/MA: Addison-Wesley, 1979. - ISBN 0-201-02988-X .
- John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Introducción a la teoría de autómatas, lenguajes y computación . - 2. - Addison Wesley , 2001. - ISBN 0-201-44124-1 .
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - M. : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .
Michael Sipser. Introducción a la Teoría de la Computación . - Boston/MA: PWS Publishing Co., 1997. - ISBN 0-534-94728-X .
Juan Martín. Introducción a los Lenguajes y la Teoría de la Computación. - McGraw Hill, 2010. - ISBN 978-0071289429 .
Rabin MO, Scott D. Finite Automata y sus problemas de decisión // IBM Journal of Research and Development. - 1959. - Abril ( vol. 3 , número 2 ). -doi : 10.1147/ rd.32.0114 .
Allan C., Avgustinov P., Christensen AS, Hendren L., Kuzins S., Lhoták O., de Moor O., Sereni D., Sittampalam G., Tibble J. Adding trace matching with free variables to AspectJ // In Actas de la 20ª Conferencia Anual ACM SIGPLAN sobre Programación Orientada a Objetos, Sistemas, Lenguajes y Aplicaciones . — San Diego, CA, EE. UU.: OOPSLA '05. ACM, Nueva York, NY, 2005. págs. 345-364. Archivado el 18 de septiembre de 2009 en Wayback Machine .

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami