Autómata finito no determinista

Tipos de máquinas de estados finitos en la teoría de autómatas

NFA para (0|1) ^*  1 (0|1) ³ .
Un DFA para ese idioma tiene al menos 16 estados.

En la teoría de autómatas , una máquina de estados finitos se denomina autómata finito determinista (DFA), si

• Cada una de sus transiciones está determinada de forma única por su estado de origen y símbolo de entrada, y
• Es necesario leer un símbolo de entrada para cada transición de estado.

Un autómata finito no determinista ( NFA ), o máquina de estados finitos no determinista , no necesita obedecer estas restricciones. En particular, cada DFA es también un NFA. A veces, el término NFA se utiliza en un sentido más estricto, haciendo referencia a un NFA que no es un DFA, pero no en este artículo.

Utilizando el algoritmo de construcción de subconjuntos , cada NFA se puede traducir a un DFA equivalente; es decir, un DFA que reconoce el mismo lenguaje formal . ^[1] Al igual que los DFA, los NFA solo reconocen lenguajes regulares .

Los NFA fueron introducidos en 1959 por Michael O. Rabin y Dana Scott ^[2] , quienes también demostraron su equivalencia con los DFA. Los NFA se utilizan en la implementación de expresiones regulares : la construcción de Thompson es un algoritmo para compilar una expresión regular en un NFA que puede realizar de manera eficiente la coincidencia de patrones en cadenas. Por el contrario, el algoritmo de Kleene se puede utilizar para convertir un NFA en una expresión regular (cuyo tamaño es generalmente exponencial en el autómata de entrada).

Los NFA se han generalizado de múltiples maneras, por ejemplo, autómatas finitos no deterministas con ε-moves, transductores de estados finitos , autómatas de empuje , autómatas alternantes , ω-autómatas y autómatas probabilísticos . Además de los DFA, otros casos especiales conocidos de NFA son los autómatas finitos no ambiguos (UFA) y los autómatas finitos autoverificantes (SVFA).

Introducción informal

Existen al menos dos formas de describir el comportamiento de un factor de activación de red (NFA), y ambas son equivalentes. La primera forma hace uso del no determinismo en el nombre de un factor de activación de red. Para cada símbolo de entrada, el factor de activación de red pasa a un nuevo estado hasta que se hayan consumido todos los símbolos de entrada. En cada paso, el autómata "elige" de manera no determinista una de las transiciones aplicables. Si existe al menos una "ejecución afortunada", es decir, alguna secuencia de elecciones que conduzca a un estado de aceptación después de consumir completamente la entrada, se acepta. De lo contrario, es decir, si ninguna secuencia de elecciones puede consumir toda la entrada ^[3] y conducir a un estado de aceptación, la entrada se rechaza. ^{[4] : 19  [5] : 319}

En el segundo modo, el NFA consume una cadena de símbolos de entrada, uno por uno. En cada paso, siempre que dos o más transiciones sean aplicables, se "clona" a sí mismo en un número apropiado de copias, cada una siguiendo una transición diferente. Si no es aplicable ninguna transición, la copia actual está en un callejón sin salida y "muere". Si, después de consumir la entrada completa, alguna de las copias está en un estado de aceptación, la entrada se acepta; de lo contrario, se rechaza. ^{[4] : 19–20  [6] : 48  [7] : 56}

Definición formal

Para una introducción más elemental de la definición formal, véase teoría de autómatas .

Autómata

Un NFA se representa formalmente mediante una tupla de 5 , , que consta de ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$

• un conjunto finito de estados , ${\displaystyle Q}$
• un conjunto finito de símbolos de entrada , ${\displaystyle \Sigma }$
• una función de transición  :, ${\displaystyle \delta }$ ${\displaystyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$
• un estado inicial (o de inicio ) , y ${\displaystyle q_{0}\in Q}$
• un conjunto de estados que se distinguen como estados de aceptación (o finales ) . ${\displaystyle F}$ ${\displaystyle F\subseteq Q}$

Aquí, denota el conjunto potencia de . ${\displaystyle {\mathcal {P}}(Q)}$ ${\displaystyle Q}$

Idioma reconocido

Dado un NFA , su idioma reconocido se denota por y se define como el conjunto de todas las cadenas sobre el alfabeto que son aceptadas por . ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$ ${\displaystyle L(M)}$ ${\displaystyle \Sigma }$ ${\displaystyle M}$

En correspondencia con las explicaciones informales anteriores, existen varias definiciones formales equivalentes de una cadena que son aceptadas por : ${\displaystyle w=a_{1}a_{2}...a_{n}}$ ${\displaystyle M}$

• ${\displaystyle w}$se acepta si existe una secuencia de estados, , tal que: ${\displaystyle r_{0},r_{1},...,r_{n}}$ ${\displaystyle Q}$
  1. ${\displaystyle r_{0}=q_{0}}$
  2. ${\displaystyle r_{i+1}\in \delta (r_{i},a_{i+1})}$, para ${\displaystyle i=0,\ldots ,n-1}$
  3. ${\displaystyle r_{n}\in F}$.

En palabras, la primera condición dice que la máquina comienza en el estado de inicio . La segunda condición dice que dado cada carácter de la cadena , la máquina pasará de un estado a otro según la función de transición . La última condición dice que la máquina acepta si la última entrada de hace que la máquina se detenga en uno de los estados de aceptación. Para que sea aceptado por , no se requiere que cada secuencia de estados termine en un estado de aceptación, es suficiente con que lo haga. De lo contrario, es decir , si es imposible en absoluto llegar de a un estado de siguiendo , se dice que el autómata rechaza la cadena. El conjunto de cadenas que acepta es el lenguaje reconocido por y este lenguaje se denota por . ^{[5] : 320  [6] : 54} ${\displaystyle q_{0}}$ ${\displaystyle w}$ ${\displaystyle \delta }$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle M}$ ${\displaystyle q_{0}}$ ${\displaystyle F}$ ${\displaystyle w}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle L(M)}$

• Alternativamente, se acepta si , donde se define recursivamente por: ${\displaystyle w}$ ${\displaystyle \delta ^{*}(q_{0},w)\cap F\not =\emptyset }$ ${\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}$
  1. ${\displaystyle \delta ^{*}(r,\epsilon )=\{r\}}$¿Dónde está la cadena vacía, y ${\displaystyle \epsilon }$
  2. ${\displaystyle \delta ^{*}(r,xa)=\bigcup _{r'\in \delta ^{*}(r,x)}\delta (r',a)}$Para todos . ${\displaystyle x\in \Sigma ^{*},a\in \Sigma }$

En palabras, es el conjunto de todos los estados a los que se puede llegar desde el estado consumiendo la cadena . La cadena se acepta si se puede llegar a algún estado de aceptación en desde el estado inicial consumiendo . ^{[4] : 21  [7] : 59} ${\displaystyle \delta ^{*}(r,x)}$ ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle w}$ ${\displaystyle F}$ ${\displaystyle q_{0}}$ ${\displaystyle w}$

Estado inicial

La definición de autómata anterior utiliza un único estado inicial , lo cual no es necesario. A veces, los NFA se definen con un conjunto de estados iniciales. Existe una construcción sencilla que traduce un NFA con múltiples estados iniciales a un NFA con un único estado inicial, lo que proporciona una notación conveniente.

Ejemplo

El siguiente autómata , con un alfabeto binario, determina si la entrada termina en 1. Sea donde la función de transición se puede definir mediante esta tabla de transición de estados (véase la imagen superior izquierda): ${\displaystyle M}$ ${\displaystyle M=(\{p,q\},\{0,1\},\delta ,p,\{q\})}$ ${\displaystyle \delta }$

Dado que el conjunto contiene más de un estado, no es determinista. El lenguaje de se puede describir mediante el lenguaje regular dado por la expresión regular . ${\displaystyle \delta (p,1)}$ ${\displaystyle M}$ ${\displaystyle M}$ (0|1)*1

En la imagen inferior se muestran todas las posibles secuencias de estados para la cadena de entrada "1011". La cadena se acepta porque una secuencia de estados satisface la definición anterior; no importa que otras secuencias no lo hagan. La imagen se puede interpretar de un par de maneras: ${\displaystyle M}$

• En términos de la explicación de la "carrera de suerte" anterior, cada camino en la imagen denota una secuencia de opciones de . ${\displaystyle M}$
• En términos de la explicación de la "clonación", cada columna vertical muestra todos los clones en un punto dado en el tiempo, múltiples flechas que emanan de un nodo indican clonación, un nodo sin flechas que emanan indica la "muerte" de un clon. ${\displaystyle M}$

La posibilidad de leer la misma imagen de dos maneras también indica la equivalencia de ambas explicaciones anteriores.

• Considerando la primera de las definiciones formales anteriores, se acepta "1011" ya que al leerlo puede recorrer la secuencia de estados , que satisface las condiciones 1 a 3. ${\displaystyle M}$ ${\displaystyle \langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle }$
• Respecto de la segunda definición formal, el cálculo de abajo hacia arriba muestra que , por lo tanto , por lo tanto , por lo tanto y por lo tanto ; dado que ese conjunto no es disjunto de , se acepta la cadena "1011". ${\displaystyle \delta ^{*}(p,\epsilon )=\{p\}}$ ${\displaystyle \delta ^{*}(p,1)=\delta (p,1)=\{p,q\}}$ ${\displaystyle \delta ^{*}(p,10)=\delta (p,0)\cup \delta (q,0)=\{p\}\cup \{\}}$ ${\displaystyle \delta ^{*}(p,101)=\delta (p,1)=\{p,q\}}$ ${\displaystyle \delta ^{*}(p,1011)=\delta (p,1)\cup \delta (q,1)=\{p,q\}\cup \{\}}$ ${\displaystyle \{q\}}$

Por el contrario, la cadena "10" es rechazada por (todas las secuencias de estados posibles para esa entrada se muestran en la imagen superior derecha), ya que no hay forma de alcanzar el único estado de aceptación, , leyendo el símbolo 0 final. Si bien se puede alcanzar después de consumir el "1" inicial, esto no significa que se acepte la entrada "10"; más bien, significa que se aceptaría una cadena de entrada "1". ${\displaystyle M}$ ${\displaystyle q}$ ${\displaystyle q}$

Equivalencia con DFA

Un autómata finito determinista (AFD) puede considerarse como un tipo especial de AFN, en el que para cada estado y símbolo, la función de transición tiene exactamente un estado. Por lo tanto, es evidente que todo lenguaje formal que pueda ser reconocido por un AFD puede ser reconocido por un AFN.

Por el contrario, para cada NFA, existe un DFA que reconoce el mismo lenguaje formal. El DFA se puede construir utilizando la construcción de conjuntos de potencias .

Este resultado muestra que los NFA, a pesar de su flexibilidad adicional, no pueden reconocer lenguajes que no pueden ser reconocidos por algunos DFA. También es importante en la práctica para convertir NFA más fáciles de construir en DFA ejecutables de manera más eficiente. Sin embargo, si el NFA tiene n estados, el DFA resultante puede tener hasta 2 ⁿ estados, lo que a veces hace que la construcción sea poco práctica para NFA grandes.

NFA con movimientos ε

El autómata finito no determinista con ε-movimientos (NFA-ε) es una generalización adicional del NFA. En este tipo de autómata, la función de transición se define adicionalmente en la cadena vacía ε. Una transición sin consumir un símbolo de entrada se denomina ε-transición y se representa en los diagramas de estado mediante una flecha etiquetada como "ε". Las ε-transiciones proporcionan una forma conveniente de modelar sistemas cuyos estados actuales no se conocen con precisión: es decir, si estamos modelando un sistema y no está claro si el estado actual (después de procesar alguna cadena de entrada) debe ser q o q', entonces podemos agregar una ε-transición entre estos dos estados, colocando así al autómata en ambos estados simultáneamente.

Definición formal

Un NFA-ε se representa formalmente mediante una tupla de 5 , , que consta de ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$

• un conjunto finito de estados ${\displaystyle Q}$
• un conjunto finito de símbolos de entrada llamado alfabeto ${\displaystyle \Sigma }$
• una función de transición ${\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow {\mathcal {P}}(Q)}$
• un estado inicial (o de inicio ) ${\displaystyle q_{0}\in Q}$
• un conjunto de estados que se distinguen como estados de aceptación (o finales ) . ${\displaystyle F}$ ${\displaystyle F\subseteq Q}$

Aquí, denota el conjunto potencia de y denota cadena vacía. ${\displaystyle {\mathcal {P}}(Q)}$ ${\displaystyle Q}$ ${\displaystyle \epsilon }$

ε-cierre de un estado o conjunto de estados

Para un estado , denotemos el conjunto de estados a los que se puede llegar siguiendo ε-transiciones en la función de transición , es decir, si hay una secuencia de estados tales que ${\displaystyle q\in Q}$ ${\displaystyle E(q)}$ ${\displaystyle q}$ ${\displaystyle \delta }$ ${\displaystyle p\in E(q)}$ ${\displaystyle q_{1},...,q_{k}}$

• ${\displaystyle q_{1}=q}$,
• ${\displaystyle q_{i+1}\in \delta (q_{i},\varepsilon )}$para cada uno , y ${\displaystyle 1\leq i<k}$
• ${\displaystyle q_{k}=p}$.

${\displaystyle E(q)}$se conoce como el cierre épsilon (también ε-cierre ) de . ${\displaystyle q}$

El ε-cierre de un conjunto de estados de un NFA se define como el conjunto de estados alcanzables desde cualquier estado en las siguientes ε-transiciones. Formalmente, para , defina . ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P\subseteq Q}$ ${\displaystyle E(P)=\bigcup \limits _{q\in P}E(q)}$

Función de transición extendida

De manera similar a NFA sin ε-moves, la función de transición de un NFA-ε se puede extender a cadenas. De manera informal, denota el conjunto de todos los estados que el autómata puede haber alcanzado al comenzar en el estado y leer la cadena . La función se puede definir de manera recursiva de la siguiente manera. ${\displaystyle \delta }$ ${\displaystyle \delta ^{*}(q,w)}$ ${\displaystyle q\in Q}$ ${\displaystyle w\in \Sigma ^{*}.}$ ${\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}$

• ${\displaystyle \delta ^{*}(q,\varepsilon )=E(q)}$, para cada estado y donde denota el cierre épsilon; ${\displaystyle q\in Q,}$ ${\displaystyle E}$

De manera informal: leer la cadena vacía puede llevar al autómata del estado a cualquier estado del cierre épsilon de ${\displaystyle q}$ ${\displaystyle q.}$

• ${\textstyle \delta ^{*}(q,wa)=\bigcup _{r\in \delta ^{*}(q,w)}E(\delta (r,a)),}$Para cada estado, cada cadena y cada símbolo. ${\displaystyle q\in Q,}$ ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle a\in \Sigma .}$

De manera informal: leer la cadena puede llevar al autómata de un estado a cualquier estado en el conjunto calculado recursivamente ; después de eso, leer el símbolo puede llevarlo de un estado a cualquier estado en el cierre épsilon de ${\displaystyle w}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle \delta ^{*}(q,w)}$ ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle \delta (r,a).}$

Se dice que el autómata acepta una cadena si ${\displaystyle w}$

${\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \emptyset ,}$

es decir, si la lectura puede llevar al autómata desde su estado inicial a algún estado de aceptación en ^{[4] : ​​25} ${\displaystyle w}$ ${\displaystyle q_{0}}$ ${\displaystyle F.}$

Ejemplo

El diagrama de estados para M

Sea un NFA-ε, con un alfabeto binario, que determina si la entrada contiene un número par de 0 o un número par de 1. Nótese que 0 ocurrencias también es un número par de ocurrencias. ${\displaystyle M}$

En notación formal, sea donde la relación de transición se puede definir mediante esta tabla de transición de estados : $${\displaystyle M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\delta ,S_{0},\{S_{1},S_{3}\})}$$ ${\displaystyle \delta }$

${\displaystyle M}$puede verse como la unión de dos DFA : uno con estados y el otro con estados . El lenguaje de puede describirse mediante el lenguaje regular dado por esta expresión regular . Definimos usando ε-moves pero puede definirse sin usar ε-moves. ${\displaystyle \{S_{1},S_{2}\}}$ ${\displaystyle \{S_{3},S_{4}\}}$ ${\displaystyle M}$ ${\displaystyle (1^{*}01^{*}0)^{*}\cup (0^{*}10^{*}1)^{*}}$ ${\displaystyle M}$ ${\displaystyle M}$

Equivalencia con NFA

Para demostrar que NFA-ε es equivalente a NFA, primero observe que NFA es un caso especial de NFA-ε, por lo que queda demostrar que para cada NFA-ε, existe un NFA equivalente.

Dado un NFA con movimientos épsilon, defina un NFA donde ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F),}$ ${\displaystyle M'=(Q,\Sigma ,\delta ',q_{0},F'),}$

${\displaystyle F'={\begin{cases}F\cup \{q_{0}\}&{\text{ if }}E(q_{0})\cap F\neq \{\}\\F&{\text{ otherwise }}\\\end{cases}}}$

y

${\displaystyle \delta '(q,a)=\delta ^{*}(q,a)}$para cada estado y cada símbolo utilizando la función de transición extendida definida anteriormente. ${\displaystyle q\in Q}$ ${\displaystyle a\in \Sigma ,}$ ${\displaystyle \delta ^{*}}$

Hay que distinguir las funciones de transición de y , es decir, y y sus extensiones a cadenas, y respectivamente. Por construcción, no tiene ε-transiciones. ${\displaystyle M}$ ${\displaystyle M',}$ ${\displaystyle \delta }$ ${\displaystyle \delta ',}$ ${\displaystyle \delta }$ ${\displaystyle \delta '^{*},}$ ${\displaystyle M'}$

Se puede demostrar que para cada cuerda , por inducción sobre la longitud de ${\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}$ ${\displaystyle w\neq \varepsilon }$ ${\displaystyle w.}$

En base a esto, se puede demostrar que si, y sólo si, para cada cadena ${\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}}$ ${\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \{\},}$ ${\displaystyle w\in \Sigma ^{*}:}$

• Si esto se desprende de la definición de ${\displaystyle w=\varepsilon ,}$ ${\displaystyle F'.}$
• De lo contrario, deje con y ${\displaystyle w=va}$ ${\displaystyle v\in \Sigma ^{*}}$ ${\displaystyle a\in \Sigma .}$

Desde y tenemos todavía tenemos que mostrar la dirección " ". ${\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}$ ${\displaystyle F\subseteq F',}$ $${\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Leftarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\};}$$ ${\displaystyle \Rightarrow }$

• Si contiene un estado en entonces contiene el mismo estado, que se encuentra en . ${\displaystyle \delta '^{*}(q_{0},w)}$ ${\displaystyle F'\setminus \{q_{0}\},}$ ${\displaystyle \delta ^{*}(q_{0},w)}$ ${\displaystyle F}$
• Si contiene y entonces también contiene un estado, a saber: ${\displaystyle \delta '^{*}(q_{0},w)}$ ${\displaystyle q_{0},}$ ${\displaystyle q_{0}\in F,}$ ${\displaystyle \delta ^{*}(q_{0},w)}$ ${\displaystyle F,}$ ${\displaystyle q_{0}.}$
• Si contiene y pero entonces existe un estado en , y el mismo estado debe estar en ^{[4] : 26–27} ${\displaystyle \delta '^{*}(q_{0},w)}$ ${\displaystyle q_{0},}$ ${\displaystyle q_{0}\not \in F,}$ ${\displaystyle q_{0}\in F',}$ ${\displaystyle E(q_{0})\cap F}$ ${\textstyle \delta ^{*}(q_{0},w)=\bigcup _{r\in \delta ^{*}(q,v)}E(\delta (r,a)).}$

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

Propiedades del cierre

NFA compuesto que acepta la unión de los lenguajes de algunos NFAs dados N ( s ) y N ( t ) . Para una cadena de entrada w en la unión del lenguaje, el autómata compuesto sigue una ε-transición desde q hasta el estado inicial (círculo de color de la izquierda) de un subautómata apropiado — N ( s ) o N ( t ) — que, siguiendo w , puede alcanzar un estado de aceptación (círculo de color de la derecha); desde allí, se puede alcanzar el estado f mediante otra ε-transiciones. Debido a las ε-transiciones, el NFA compuesto es propiamente no determinista incluso si tanto N ( s ) como N ( t ) fueran DFAs; viceversa, construir un DFA para el lenguaje de unión (incluso de dos DFAs) es mucho más complicado.

El conjunto de idiomas reconocidos por los NFA se cierra con las siguientes operaciones. Estas operaciones de cierre se utilizan en el algoritmo de construcción de Thompson , que construye un NFA a partir de cualquier expresión regular . También se pueden utilizar para demostrar que los NFA reconocen exactamente los idiomas regulares .

• Unión (cf. imagen); es decir, si el lenguaje L ₁ es aceptado por algún NFA A ₁ y L ₂ por algún A ₂ , entonces se puede construir un NFA A _{u que acepte el lenguaje} L ₁ ∪ L ₂ .
• Intersección; de manera similar, a partir de A ₁ y A ₂ se puede construir un NFA A _{i que acepta} L ₁ ∩ L ₂ .
• Concatenación
• Negación; de manera similar, a partir de A ₁ se puede construir un NFA A _{n que acepte Σ} ^* \ L ₁ .
• Cierre de Kleene

Dado que los NFA son equivalentes a autómatas finitos no deterministas con ε-movimientos (NFA-ε), los cierres anteriores se prueban utilizando propiedades de cierre de NFA-ε.

Propiedades

La máquina comienza en el estado inicial especificado y lee una cadena de símbolos de su alfabeto . El autómata utiliza la función de transición de estado Δ para determinar el siguiente estado utilizando el estado actual y el símbolo recién leído o la cadena vacía. Sin embargo, "el siguiente estado de un NFA depende no solo del evento de entrada actual, sino también de un número arbitrario de eventos de entrada posteriores. Hasta que estos eventos posteriores ocurran, no es posible determinar en qué estado se encuentra la máquina". ^[8] Si, cuando el autómata ha terminado de leer, se dice que el NFA acepta la cadena, de lo contrario se dice que rechaza la cadena.

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

Para cada 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 con el fin de implementar una máquina (quizás) más simple. Esto se puede realizar utilizando la construcción de conjuntos de potencias , que puede llevar a un aumento exponencial en el número de estados necesarios. Para una prueba formal de la construcción de conjuntos de potencias, consulte el artículo Construcción de conjuntos de potencias .

Implementación

Hay muchas maneras de implementar un NFA:

• Convertir al DFA equivalente. En algunos casos, esto puede provocar un aumento exponencial en el número de estados. ^[9]
• Mantenga una estructura de datos de conjunto de todos los estados en los que el NFA podría estar actualmente. En el consumo de un símbolo de entrada, una los resultados de la función de transición aplicada a todos los estados actuales para obtener el conjunto de estados siguientes; si se permiten ε-movimientos, incluya todos los estados alcanzables por dicho movimiento (ε-cierre). Cada paso requiere como máximo s ² cálculos, donde s es el número de estados del NFA. En el consumo del último símbolo de entrada, si uno de los estados actuales es un estado final, la máquina acepta la cadena. Una cadena de longitud n se puede procesar en tiempo O ( ns ² ), ^{[7] : 153} y espacio O ( s ).
• Crear múltiples copias. Para cada decisión de n vías, el NFA crea hasta n −1 copias de la máquina. Cada una ingresará en un estado separado. Si, al consumir el último símbolo de entrada, al menos una copia del NFA está en el estado de aceptación, el NFA aceptará. (Esto también requiere almacenamiento lineal con respecto a la cantidad de estados del NFA, ya que puede haber una máquina para cada estado del NFA).
• Propagación explícita de tokens a través de la estructura de transición del NFA y coincidencias cada vez que un token alcanza el estado final. Esto a veces es útil cuando el NFA debe codificar contexto adicional sobre los eventos que activaron la transición. (Para una implementación que utiliza esta técnica para realizar un seguimiento de las referencias de objetos, consulte Tracematches). ^[10]

Complejidad

• Se puede resolver en tiempo lineal el problema del vacío para NFA, es decir, comprobar si el lenguaje de un NFA dado está vacío. Para ello, podemos realizar simplemente una búsqueda en profundidad a partir del estado inicial y comprobar si se puede alcanzar algún estado final.
• Es PSPACE -completo probar, dado un NFA, si es universal , es decir, si hay una cadena que no acepta. ^[11] En consecuencia, lo mismo es cierto para el problema de inclusión , es decir, dados dos NFA, ¿el lenguaje de uno es un subconjunto del lenguaje del otro?
• Dado como entrada un NFA A y un entero n, el problema de conteo de determinar cuántas palabras de longitud n son aceptadas por A es intratable; es #P -hard . De hecho, este problema es completo (bajo reducciones parsimoniosas ) para la clase de complejidad SpanL. ^[12]

Aplicación de la NFA

Los NFA y los DFA son equivalentes en el sentido de que si un lenguaje es reconocido por un NFA, también es reconocido por un DFA y viceversa. El establecimiento de dicha equivalencia es importante y útil. Es útil porque construir un NFA para reconocer un lenguaje dado es a veces mucho más fácil que construir un DFA para ese lenguaje. Es importante porque los NFA se pueden utilizar para reducir la complejidad del trabajo matemático requerido para establecer muchas propiedades importantes en la teoría de la computación . Por ejemplo, es mucho más fácil probar propiedades de clausura de lenguajes regulares utilizando NFA que DFA.

Véase también

• Autómata finito determinista
• Autómata finito no determinista de dos vías
• Autómata de empuje hacia abajo
• Máquina de Turing no determinista

Notas

1. Martin, John (2010). Introducción a los lenguajes y la teoría de la computación . McGraw Hill. pág. 108. ISBN. 978-0071289429.
2. Rabin, MO; Scott, D. (abril de 1959). "Autómatas finitos y sus problemas de decisión". Revista IBM de investigación y desarrollo . 3 (2): 114–125. doi :10.1147/rd.32.0114.
3. Una secuencia de elección puede conducir a un "callejón sin salida" donde no hay ninguna transición aplicable para el símbolo de entrada actual; en este caso, se considera fallida.
4. John E. Hopcroft y Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación. Lectura/MA: Addison-Wesley. ISBN 0-201-02988-X.
5. Alfred V. Aho y John E. Hopcroft y Jeffrey D. Ullman (1974). El diseño y análisis de algoritmos informáticos . Reading/MA: Addison-Wesley. ISBN 0-201-00029-6.
6. Michael Sipser (1997). Introducción a la teoría de la computación. Boston/MA: PWS Publishing Co. ISBN 0-534-94728-X.
7. John E. Hopcroft y Rajeev Motwani y Jeffrey D. Ullman (2003). Introducción a la teoría de autómatas, lenguajes y computación (PDF) . Upper Saddle River/NJ: Addison Wesley. ISBN 0-201-44124-1.
8. Diccionario gratuito en línea de computación FOLDOC, Máquina de estados finitos
9. Chris Calabro (27 de febrero de 2005). "Explosión de NFA a DFA" (PDF) . cseweb.ucsd.edu . Consultado el 6 de marzo de 2023 .
10. Allan, C., Avgustinov, P., Christensen, AS, Hendren, L., Kuzins, S., Lhoták, O., de Moor, O., Sereni, D., Sittampalam, G. y Tibble, J. 2005. Adición de coincidencia de trazas con variables libres a AspectJ Archivado el 18 de septiembre de 2009 en Wayback Machine . En Actas de la 20.ª Conferencia anual ACM SIGPLAN sobre programación orientada a objetos, sistemas, lenguajes y aplicaciones (San Diego, CA, EE. UU., 16 al 20 de octubre de 2005). OOPSLA '05. ACM, Nueva York, NY, 345-364.
11. Históricamente mostrado en: Meyer, AR; Stockmeyer, LJ (1972-10-25). "El problema de equivalencia para expresiones regulares con elevación al cuadrado requiere espacio exponencial". Actas del 13.º Simposio Anual sobre Teoría de Conmutación y Autómatas (SWAT) . EE. UU.: IEEE Computer Society: 125–129. doi :10.1109/SWAT.1972.29.Para una presentación moderna, consulte [1]
12. Álvarez, Carme; Jenner, Birgit (4 de enero de 1993). "Una clase de conteo en el espacio logarítmico muy difícil". Ciencias Informáticas Teóricas . 107 (1): 3–30. doi :10.1016/0304-3975(93)90252-O. ISSN  0304-3975.

Referencias

• MO Rabin y D. Scott, "Autómatas finitos y sus problemas de decisión", IBM Journal of Research and Development , 3 :2 (1959), págs. 115–125.
• Michael Sipser, Introducción a la teoría de la computación . PWS, Boston. 1997. ISBN 0-534-94728-X . (véase la sección 1.2: No determinismo, págs. 47-63). 
• John E. Hopcroft y Jeffrey D. Ullman, Introducción a la teoría de autómatas, lenguajes y computación , Addison-Wesley Publishing, Reading, Massachusetts, 1979. ISBN 0-201-02988-X . (Véase el capítulo 2.)