Autómata finito no determinista

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

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

Un autómata finito no determinista ( AFN ), o máquina de estados finitos no determinista , no necesita cumplir estas restricciones. En particular, todo autómata finito determinista (AFD) es también un AFN. A veces, el término AFN se usa en un sentido más restringido, refiriéndose a un AFN que no es un AFD, 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 autómatas finitos no deterministas (AFND) fueron introducidos en 1959 por Michael O. Rabin y Dana Scott , ^{[ 2 ]} quienes también demostraron su equivalencia con los autómatas finitos deterministas (AFD). Los AFND se utilizan en la implementación de expresiones regulares : la construcción de Thompson es un algoritmo para compilar una expresión regular a un AFND que puede realizar eficientemente la coincidencia de patrones en cadenas. Por el contrario, el algoritmo de Kleene se puede utilizar para convertir un AFND en una expresión regular (cuyo tamaño suele ser exponencial en el autómata de entrada).

Los autómatas finitos no deterministas ( AFND) se han generalizado de diversas maneras, por ejemplo, mediante autómatas finitos no deterministas con movimientos ε , transductores de estados finitos , autómatas de pila , autómatas alternantes , autómatas ω y autómatas probabilísticos . Además de los autómatas finitos deterministas (AFD), otros casos especiales conocidos de AFND son los autómatas finitos no ambiguos (AFU) y los autómatas finitos autoverificables (AFVS).

Introducción informal

Hay al menos dos formas equivalentes de describir el comportamiento de un autómata finito no determinista (AFND). La primera utiliza el no determinismo inherente al nombre de AFND. Para cada símbolo de entrada, el AFND transita a un nuevo estado hasta que todos los símbolos de entrada se hayan consumido. En cada paso, el autómata "elige" de forma no determinista una de las transiciones aplicables. Si existe al menos una "secuencia afortunada", es decir, alguna secuencia de elecciones que conduzca a un estado de aceptación después de consumir completamente la entrada, esta 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 ]}^{[ 5 ]}^{: 319}^{[ 6 ]}

En la segunda forma, el autómata finito no determinista (AFND) consume una cadena de símbolos de entrada, uno por uno. En cada paso, cuando dos o más transiciones son aplicables, se "clona" en tantas copias como corresponda, cada una siguiendo una transición diferente. Si ninguna transición es aplicable, la copia actual se encuentra en un callejón sin salida y "muere". Si, después de consumir la entrada completa, alguna de las copias está en estado de aceptación, la entrada se acepta; de lo contrario, se rechaza. ^{[ 4 ]}^{[ 7 ]}^{[ 6 ]}

Definición formal

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

Autómata

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

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

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

Idioma reconocido

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

En correspondencia aproximada con las explicaciones informales anteriores , existen varias definiciones formales equivalentes de una cadena. $w=a_{1}a_{2}...a_{n}$ ser aceptado por $M$ :

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

En otras palabras, la primera condición dice que la máquina se inicia en el estado de inicio.

q_{0}

. La segunda condición dice que dado cada carácter de la cadena

w

La máquina pasará de un estado a otro según la función de transición.

\delta

. La última condición dice que la máquina acepta

w

si la última entrada de

w

hace que la máquina se detenga en uno de los estados de aceptación. Para que

w

ser aceptado por

M

, no es necesario que cada secuencia de estados termine en un estado de aceptación, es suficiente si una lo hace. De lo contrario, es decir , si es imposible en absoluto llegar desde

q_{0}

a un estado desde

F

siguiendo

w

Se dice que el autómata rechaza la cadena. El conjunto de cadenas

M

acepta es el idioma reconocido por

M

y este lenguaje se denota por

L(M)

. ^{[ 5 ]}^{: 320}^{[ 8 ]}

Alternativamente, $w$ $w$ se acepta si $\delta ^{*}(q_{0},w)\cap F\not =\emptyset$ $\delta ^{*}(q_{0},w)\cap F\not =\emptyset$ , dónde $\delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)$ $\delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)$ se define recursivamente por:
1. $\delta ^{*}(r,\varepsilon )=\{r\}$ dónde $\varepsilon$ es la cadena vacía y
2. $\delta ^{*}(r,xa)=\bigcup _{r'\in \delta ^{*}(r,x)}\delta (r',a)$ a pesar de $x\in \Sigma ^{*},a\in \Sigma$ .

En palabras,

\delta ^{*}(r,x)

es el conjunto de todos los estados alcanzables desde el estado

r

al consumir la cadena

x

. La cadena

w

es aceptado si algún estado que lo acepta en

F

Se puede alcanzar desde el estado inicial.

q_{0}

al consumir

w

. ^{[ 9 ]}^{[ 10 ]}

Estado inicial

La definición de autómata anterior utiliza un único estado inicial , lo cual no es necesario. En ocasiones, los autómatas finitos no deterministas (AFND) se definen con un conjunto de estados iniciales. Existe una construcción sencilla que transforma un AFND con múltiples estados iniciales en un AFND con un único estado inicial, lo que proporciona una notación conveniente.

Isomorfismo

Un isomorfismo $\varphi$ de un autómata $(Q,\Sigma ,\delta ,q_{0},F)$ a un autómata $(Q',\Sigma ,\delta ',q'_{0},F')$ es una aplicación biyectiva $\varphi :Q\to Q'$ de tal manera que

$\varphi (q_{0})=q'_{0}$ ,
$q\in F$ si, y solo si, $\varphi (q)\in F'$ , para cada $q\in Q$ , y
$r\in \delta (q,a)$ si, y solo si, $\varphi (r)\in \delta '(\varphi (q),a)$ , para cada $q,r\in Q$ y $a\in \Sigma$ .

Intuitivamente, dos autómatas son isomorfos si comparten el mismo alfabeto y uno se puede obtener renombrando sistemáticamente los estados del otro.

Ejemplo

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

{\begin{array}{|c|cc|}{\bcancel {{}_{\text{State}}\quad {}^{\text{Input}}}}&0&1\\\hline p&\{p\}&\{p,q\}\\q&\emptyset &\emptyset \end{array}}

Desde el conjunto $\delta (p,1)$ Contiene más de un estado, $M$ es no determinista. El lenguaje de $M$ puede describirse mediante el lenguaje regular dado por la expresión regular(0|1)*1 .

En la imagen inferior se muestran todas las secuencias de estados posibles para la cadena de entrada "1011".

La cadena es aceptada por $M$ ya que una secuencia de estados satisface la definición anterior; no importa que otras secuencias no la cumplan. La imagen puede interpretarse de varias maneras:

En términos de la explicación anterior de "racha de suerte", cada camino en la imagen denota una secuencia de elecciones de $M.$
En cuanto a la explicación de la "clonación", cada columna vertical muestra todos los clones de $M$ en un momento dado; varias flechas que emanan de un nodo indican clonación, y un nodo sin flechas que emanan indica la "muerte" de un clon.

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

Considerando la primera de las definiciones formales anteriores , "1011" es aceptado ya que al leerlo $M$ puede recorrer la secuencia de estados. $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$ , que satisface las condiciones 1 a 3.
En cuanto a la segunda definición formal, el cálculo ascendente muestra que $\delta ^{*}(p,\varepsilon )=\{p\}$ , por eso $\delta ^{*}(p,1)=\delta (p,1)=\{p,q\}$ , por eso $\delta ^{*}(p,10)=\delta (p,0)\cup \delta (q,0)=\{p\}\cup \{\}$ , por eso $\delta ^{*}(p,101)=\delta (p,1)=\{p,q\}$ y por lo tanto $\delta ^{*}(p,1011)=\delta (p,1)\cup \delta (q,1)=\{p,q\}\cup \{\}$ ; puesto que ese conjunto no es disjunto de $\{q\}$ , la cadena "1011" es aceptada.

Por el contrario, la cadena "10" es rechazada por $M$ (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, $q$ , leyendo el símbolo 0 final. Si bien se puede alcanzar $q$ después de consumir el "1" inicial, esto no significa que la entrada "10" sea aceptada; más bien, significa que una cadena de entrada "1" sería aceptada.

Equivalencia con DFA

Un autómata finito determinista (AFD) puede considerarse un tipo especial de autómata finito no determinista (AFND), 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 AFND.

Por el contrario, para cada autómata finito no determinista (AFND), existe un autómata finito determinista (AFD) que reconoce el mismo lenguaje formal. El AFD se puede construir utilizando la construcción de conjunto potencia .

Este resultado demuestra que los autómatas finitos no deterministas (AFND), a pesar de su mayor flexibilidad, no pueden reconocer lenguajes que no sean reconocidos por algunos autómatas finitos deterministas (AFD). Esto también es importante en la práctica para convertir AFND, más fáciles de construir, en AFD más eficientes. Sin embargo, si el AFND tiene n estados, el AFD resultante puede tener hasta 2n ^estados , lo que a veces dificulta la construcción para AFND de gran tamaño.

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 sobre la cadena vacía ε. Una transición que no consume un símbolo de entrada se denomina transición ε y se representa en los diagramas de estados 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 una cadena de entrada) debería 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 5- tupla , $(Q,\Sigma ,\delta ,q_{0},F)$ , que consta de

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

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

ε-cierre de un estado o conjunto de estados

Para un estado $q\in Q$ , dejar $E(q)$ denotamos el conjunto de estados que son alcanzables desde $q$ siguiendo las transiciones ε en la función de transición $\delta$ , es decir, $p\in E(q)$ si hay una secuencia de estados $q_{1},...,q_{k}$ de tal manera que

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

$E(q)$ se conoce como el cierre épsilon , (también cierre ε ) de $q$ .

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

Función de transición extendida

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

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

De manera informal: leer la cadena vacía puede hacer que el autómata salga del estado

q

a cualquier estado del cierre épsilon de

q.

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

De manera informal: leyendo la cadena

w

puede conducir el autómata desde el estado

q

a cualquier estado

r

en el conjunto calculado recursivamente

\delta ^{*}(q,w)

; después de eso, leyendo el símbolo

a

puede expulsarlo de

r

a cualquier estado en el cierre épsilon de

\delta (r,a).

Se dice que el autómata acepta una cadena $w$ si

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

es decir, si se está leyendo $w$ puede conducir el autómata desde su estado inicial. $q_{0}$ a algún estado que lo acepte en $F.$ ^{[ 11 ]}

Ejemplo

Dejar $M$ Sea un autómata finito no determinista (AFND) de tipo ε, con un alfabeto binario, que determine si la entrada contiene un número par de 0 o un número par de 1. Tenga en cuenta que 0 ocurrencias también es un número par de ocurrencias.

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

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

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 por demostrar que para cada NFA-ε existe un NFA equivalente.

Dado un autómata finito no determinista con movimientos épsilon $M=(Q,\Sigma ,\delta ,q_{0},F),$ Defina un NFA $M'=(Q,\Sigma ,\delta ',q_{0},F'),$ dónde

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

y

\delta '(q,a)=\delta ^{*}(q,a)

para cada estado

q\in Q

y cada símbolo

a\in \Sigma ,

utilizando la función de transición extendida

\delta ^{*}

definido anteriormente.

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

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

Sobre esta base, se puede demostrar que $\delta '^{*}(q_{0},w)\cap F'\neq \{\}$ si, y solo si, $\delta ^{*}(q_{0},w)\cap F\neq \{\},$ para cada cadena $w\in \Sigma ^{*}:$

Si $w=\varepsilon ,$ Esto se deduce de la definición de $F'.$
De lo contrario, deja $w=va$ con $v\in \Sigma ^{*}$ y $a\in \Sigma .$

De

\delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)

y

F\subseteq F',

tenemos

\delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Leftarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\};

aún tenemos que mostrar el "

\Rightarrow

" dirección.

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

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

Propiedades de cierre

Autómata finito no determinista (AFND) compuesto que acepta la unión de los lenguajes de algunos AFND dados N ( s ) y N ( t ) . Para una cadena de entrada w en la unión de lenguajes, el autómata compuesto sigue una transición ε desde q al estado inicial (círculo de color izquierdo) de un subautómata apropiado —N(s) o N ( t ) — que , siguiendo a w , puede alcanzar un *estado* de aceptación (círculo de color derecho); desde allí, se puede alcanzar el estado f mediante otra transición ε. Debido a las transiciones ε, el AFND compuesto es propiamente no determinista incluso si tanto N ( s ) como N ( t ) fueran autómatas finitos deterministas (AFD); a la inversa, construir un AFD para el lenguaje de unión (incluso de dos AFD) es mucho más complicado.

El conjunto de lenguajes reconocidos por los autómatas finitos no deterministas (AFND) es cerrado bajo las siguientes operaciones. Estas operaciones de cierre se utilizan en el algoritmo de construcción de Thompson , que construye un AFND a partir de cualquier expresión regular . También pueden utilizarse para demostrar que los AFND reconocen exactamente los lenguajes regulares .

Unión (véase la imagen); es decir, si el lenguaje L ₁ es aceptado por algún autómata finito no determinista (AFND) _A1 _y L 2 _por algún A ₂ , entonces se puede construir un AFND Au 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 acepte}L ₁ ∩ L ₂ .
Concatenación
Negación; de manera similar, a partir de A ₁ se puede construir un autómata finito no determinista A _{n que acepte Σ}^* \ L ₁ .
Cierre de Kleene

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

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 autómata finito no determinista (AFND) depende no solo del evento de entrada actual, sino también de un número arbitrario de eventos de entrada subsiguientes. Hasta que ocurran estos eventos subsiguientes, no es posible determinar en qué estado se encuentra la máquina". ^{[ 13 ]} Si, cuando el autómata ha terminado de leer, se encuentra en un estado de aceptación, se dice que el AFND acepta la cadena; de lo contrario, se dice que la rechaza.

El conjunto de todas las cadenas aceptadas por un autómata finito no determinista (AFND) es el lenguaje que acepta dicho AFND. Este lenguaje es un lenguaje regular .

Para cada autómata finito no determinista (AFND) existe un autómata finito determinista (AFD) que acepta el mismo lenguaje. Por lo tanto, es posible convertir un AFND existente en un AFD con el fin de implementar una máquina (quizás) más simple. Esto se puede realizar mediante la construcción de conjuntos potencia , lo que puede generar un aumento exponencial en el número de estados necesarios. Para una demostración formal de la construcción de conjuntos potencia, consulte el artículo correspondiente .

Implementación

Existen muchas maneras de implementar un NFA:

Convertir al DFA equivalente. En algunos casos, esto puede provocar un crecimiento exponencial en el número de estados. ^{[ 14 ]}
Mantén una estructura de datos de todos los estados en los que el NFA podría encontrarse actualmente. Al consumir un símbolo de entrada, une 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 ε, incluye todos los estados alcanzables mediante dicho movimiento (cierre ε). Cada paso requiere como máximo s ² cálculos, donde s es el número de estados del NFA. Al consumir el ú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 puede procesarse en tiempo O ( ns ² ), ^{[ 15 ]} y espacio O ( s ).
Crea múltiples copias. Para cada decisión de n vías, el autómata finito no determinista (AFND) crea hasta n − 1 copias de la máquina. Cada una entrará en un estado distinto. Si, al consumir el último símbolo de entrada, al menos una copia del AFND se encuentra en estado de aceptación, el AFND aceptará. (Esto también requiere un almacenamiento lineal con respecto al número de estados del AFND, ya que puede haber una máquina para cada estado del AFND).
Propaga explícitamente los tokens a través de la estructura de transición del NFA y realiza una coincidencia cuando un token alcanza el estado final. Esto resulta útil en ocasiones cuando el NFA debe codificar contexto adicional sobre los eventos que desencadenaron la transición. (Para una implementación que utiliza esta técnica para realizar un seguimiento de las referencias a objetos, consulte Tracematches). ^{[ 16 ]}

Complejidad

El problema de la vacuidad en un autómata finito no determinista (AFND) se puede resolver en tiempo lineal ; es decir, comprobar si el lenguaje de un AFND dado está vacío. Para ello, basta con realizar una búsqueda en profundidad desde el estado inicial y verificar si se puede alcanzar algún estado final.
Es PSPACE -completo probar, dado un AFN, si es universal , es decir, si hay una cadena que no acepta. ^{[ 17 ]} En consecuencia, lo mismo es cierto para el problema de inclusión , es decir, dados dos AFN, ¿es el lenguaje de uno un subconjunto del lenguaje del otro?
Dado como entrada un autómata finito no determinista (AFND) A y un entero n, el problema de conteo de determinar cuántas palabras de longitud n acepta A es intratable; es #P -difícil . De hecho, este problema es completo (bajo reducciones parsimoniosas ) para la clase de complejidad SpanL . ^{[ 18 ]}

Aplicación de NFA

Los autómatas finitos no deterministas (AFND) y los autómatas finitos deterministas (AFD) son equivalentes, ya que si un lenguaje es reconocido por un AFND, también lo es por un AFD, y viceversa. El establecimiento de esta equivalencia es importante y útil. Es útil porque construir un AFND para reconocer un lenguaje dado a veces es mucho más fácil que construir un AFD para ese lenguaje. Es importante porque los AFND pueden usarse para reducir la complejidad del trabajo matemático necesario para establecer muchas propiedades importantes en la teoría de la computación . Por ejemplo, es mucho más fácil demostrar las propiedades de cierre de los lenguajes regulares usando AFND que usando AFD.

Véase también

Notas

↑ Martin, John (2010). Introducción a los lenguajes y la teoría de la computación . McGraw Hill. pág. 108. ISBN 978-0071289429.
↑ Rabin y Scott 1959 .
↑ Una secuencia de elección puede conducir a un "callejón sin salida" donde no se puede aplicar ninguna transición para el símbolo de entrada actual; en este caso se considera que no ha tenido éxito.
1 2 Hopcroft y Ullman 1979 , págs. 19–20.
1 2 Alfred V. Aho, 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.
1 2 Hopcroft, Motwani y Ullman 2006 , págs. 55–6.
↑ Sipser 1997 , pág. 48.
↑ Sipser 1997 , pág. 54.
↑ Hopcroft y Ullman 1979 , pág. 21.
↑ Hopcroft, Motwani y Ullman 2006 , pág. 59.
↑ Hopcroft y Ullman 1979 , pág. 25.
↑ Hopcroft y Ullman 1979 , págs. 26–27.
↑ FOLDOC Diccionario gratuito en línea de informática, máquina de estados finitos
^ Chris Calabro (27 de febrero de 2005). "Explosión de NFA a DFA" (PDF) . cseweb.ucsd.edu . Consultado el 6 de marzo de 2023 .
↑ Hopcroft, Motwani y Ullman 2006 , págs. 154–5.
↑ Allan, C., Avgustinov, P., Christensen, AS, Hendren, L., Kuzins, S., Lhoták, O., de Moor, O., Sereni, D., Sittampalam, G., y Tibble, J. 2005. Adding trace matching with free variables to AspectJ Archived 2009-09-18 at the Wayback Machine . En Proceedings of the 20th Annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications (San Diego, CA, EE. UU., 16–20 de octubre de 2005). OOPSLA '05. ACM, Nueva York, NY, 345-364.
↑ 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". 13.º Simposio Anual sobre Teoría de Conmutación y Autómatas (SWAT 1972) . EE. UU.: IEEE Computer Society. págs. 125–129 . doi : 10.1109/SWAT.1972.29 . Para una presentación moderna, consulte
↑ Álvarez, Carme; Jenner, Birgit (1993-01-04). "Una clase de conteo de espacio logarítmico muy difícil" . Theoretical Computer Science . 107 (1): 3– 30. doi : 10.1016/0304-3975(93)90252-O . ISSN 0304-3975 .

Referencias

Rabin, MO; Scott, D. (abril de 1959). "Autómatas finitos y sus problemas de decisión". IBM Journal of Research and Development . 3 (2): 114– 125. doi : 10.1147/rd.32.0114 .
Sipser, Michael (1997). Introducción a la teoría de la computación (1.ª ed.). PWS Publishing. ISBN 978-0-534-94728-6.( Accesible para usuarios con discapacidades visuales ) (Véase §1.2: No determinismo, págs. 47–63).
Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª ed.). Addison-Wesley. ISBN 0-201-02988-X.( Accesible para usuarios con discapacidades visuales )
Hopcroft, John E .; Motwani, Rajeev ; Ullman, Jeffrey D. (2006) [1979]. Introducción a la teoría de autómatas, lenguajes y computación (3.ª ed.). Addison-Wesley. ISBN 0-321-45536-3.(Véase el capítulo 2, "Autómatas finitos".)

[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.

[FOOTNOTERabinScott1959-2] Rabin y Scott 1959 .

[3] Una secuencia de elección puede conducir a un "callejón sin salida" donde no se puede aplicar ninguna transición para el símbolo de entrada actual; en este caso se considera que no ha tenido éxito.

[FOOTNOTEHopcroftUllman197919–20-4] 1 2 Hopcroft y Ullman 1979 , págs. 19–20.

[Aho.Hopcroft.Ullman.1974-5] 1 2 Alfred V. Aho, 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.

[FOOTNOTEHopcroftMotwaniUllman200655–6-6] 1 2 Hopcroft, Motwani y Ullman 2006 , págs. 55–6.

[FOOTNOTESipser199748-7] Sipser 1997 , pág. 48.

[FOOTNOTESipser199754-8] Sipser 1997 , pág. 54.

[FOOTNOTEHopcroftUllman197921-9] Hopcroft y Ullman 1979 , pág. 21.

[FOOTNOTEHopcroftMotwaniUllman200659-10] Hopcroft, Motwani y Ullman 2006 , pág. 59.

[FOOTNOTEHopcroftUllman197925-11] Hopcroft y Ullman 1979 , pág. 25.

[FOOTNOTEHopcroftUllman197926–27-12] Hopcroft y Ullman 1979 , págs. 26–27.

[13] FOLDOC Diccionario gratuito en línea de informática, máquina de estados finitos

[14] Chris Calabro (27 de febrero de 2005). "Explosión de NFA a DFA" (PDF) . cseweb.ucsd.edu . Consultado el 6 de marzo de 2023 .

[FOOTNOTEHopcroftMotwaniUllman2006154–5-15] Hopcroft, Motwani y Ullman 2006 , págs. 154–5.

[16] Allan, C., Avgustinov, P., Christensen, AS, Hendren, L., Kuzins, S., Lhoták, O., de Moor, O., Sereni, D., Sittampalam, G., y Tibble, J. 2005. Adding trace matching with free variables to AspectJ Archived 2009-09-18 at the Wayback Machine . En Proceedings of the 20th Annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications (San Diego, CA, EE. UU., 16–20 de octubre de 2005). OOPSLA '05. ACM, Nueva York, NY, 345-364.

[17] 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". 13.º Simposio Anual sobre Teoría de Conmutación y Autómatas (SWAT 1972) . EE. UU.: IEEE Computer Society. págs. 125–129 . doi : 10.1109/SWAT.1972.29 . Para una presentación moderna, consulte

[18] Álvarez, Carme; Jenner, Birgit (1993-01-04). "Una clase de conteo de espacio logarítmico muy difícil" . Theoretical Computer Science . 107 (1): 3– 30. doi : 10.1016/0304-3975(93)90252-O . ISSN 0304-3975 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]