En la teoría de los 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
- Se requiere leer un símbolo de entrada para cada transición de estado.
Un autómata finito no determinista ( NFA ), o una 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 usa en un sentido más estricto, refiriéndose a un NFA que no es un DFA, pero no en este artículo.
Usando 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 los idiomas normales .
Los NFA fueron introducidos en 1959 por Michael O. Rabin y Dana Scott , [2] quienes también mostraron 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).
NFA se han generalizado en múltiples formas, por ejemplo, no determinista autómatas finitos con varepsilon mueve , transductores de estados finitos , autómatas de pila , autómatas alterna , ω-autómatas , y autómatas probabilístico . Además de los DFA, otros casos especiales conocidos de NFA son los autómatas finitos inequívocos (UFA) y los autómatas finitos autoverificables (SVFA).
Introducción informal
Hay varias explicaciones informales que son equivalentes.
- Un NFA, similar a un DFA , consume una cadena de símbolos de entrada. Para cada símbolo de entrada, pasa a un nuevo estado hasta que se hayan consumido todos los símbolos de entrada. En cada paso, el autómata elige arbitrariamente una de las transiciones aplicables. Si existe alguna "ejecución afortunada", es decir, alguna secuencia de opciones que conducen a un estado de aceptación después de consumir completamente la entrada, se acepta. De lo contrario, es decir, si ninguna secuencia de elección puede consumir toda la entrada [3] y conducir a un estado de aceptación, la entrada se rechaza. [4] : 19 [5] : 319
- Una vez más, una NFA consume una serie de símbolos de entrada, uno por uno. En cada paso, siempre que sean aplicables dos o más transiciones, se "clona" a sí mismo en un número apropiado de copias, cada una siguiendo una transición diferente. Si no se aplica 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
Definicion formal
Para una introducción más elemental de la definición formal, vea la teoría de autómatas .
Autómata
Una NFA está representada formalmente por una tupla de 5 ,, que consiste en
- un conjunto finito de estados.
- un conjunto finito de símbolos de entrada .
- una función de transición : .
- un estado inicial (o de inicio ).
- un conjunto de estados distinguidos como estados de aceptación (o finales ) .
Aquí, denota el conjunto de poder de.
Lenguaje reconocido
Dado un NFA , su lenguaje reconocido se denota por , y se define como un conjunto de todas las cadenas sobre el alfabeto que son aceptadas por .
En vaga correspondencia con las explicaciones informales anteriores , existen varias definiciones formales equivalentes de una cadena siendo aceptado por :
- se acepta si una secuencia de estados, , existe en tal que:
- , por
- .
- En palabras, la primera condición dice que la máquina arranca en el estado de inicio. . La segunda condición dice que dado cada carácter de cadena , la máquina pasará de un estado a otro de acuerdo con 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 poder para ser aceptado por , no se requiere que cada secuencia de estado termine en un estado de aceptación, es suficiente si uno lo hace. De lo contrario, es decir , si es imposible obtener de a un estado de Siguendolo , se dice que el autómata rechaza la cuerda. El conjunto de cuerdas acepta es el idioma reconocido por y este idioma se denota por . [5] : 320 [6] : 54
- Alternativamente, se acepta si , dónde se define de forma recursiva por:
- dónde es la cadena vacía, y
- para todos .
- En palabras, es el conjunto de todos los estados accesibles desde el estado consumiendo la cuerda . La cuerda se acepta si algún estado de aceptación en se puede acceder desde el estado de inicio consumiendo . [4] : 21 [7] : 59
Estado inicial
La definición de autómata anterior utiliza un solo estado inicial , que 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 solo estado inicial, lo que proporciona una notación conveniente.
Ejemplo
El siguiente autómata , con un alfabeto binario, determina si la entrada termina con un 1. Sea donde la función de transición puede ser definido por esta tabla de transición de estado (ver imagen superior izquierda):
Aporte Expresar | 0 | 1 |
---|---|---|
Desde el set contiene más de un estado, es no determinista. El idioma depuede ser descrito por el lenguaje regular dado por la expresión regular (0|1)*1
.
Todas las secuencias de estado posibles para la cadena de entrada "1011" se muestran en la imagen inferior. La cadena es aceptada pordado que una secuencia de estado satisface la definición anterior; no importa que otras secuencias no lo hagan. La imagen se puede interpretar de dos formas:
- En términos de la explicación anterior de "carrera afortunada", cada camino en la imagen denota una secuencia de opciones de.
- En términos de la explicación de "clonación", cada columna vertical muestra todos los clones de en un momento dado, múltiples flechas que emanan de un nodo indican clonación, un nodo sin flechas que emanan indica la "muerte" de un clon.
La posibilidad de leer la misma imagen de dos formas 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 atravesar la secuencia de estados , que cumple las condiciones 1 a 3.
- Con respecto a la segunda definición formal, el cálculo ascendente muestra que , por eso , por eso , por eso , y por lo tanto ; ya que ese conjunto no es disjunto de, se acepta la cadena "1011".
Por el contrario, la cadena "10" es rechazada por (todas las secuencias de estado 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. Tiempose puede alcanzar después de consumir el "1" inicial, esto no significa que la entrada "10" sea aceptada; más bien, significa que se aceptará una cadena de entrada "1".
Equivalencia a DFA
Un autómata finito determinista (DFA) puede verse como un tipo especial de NFA, en el que para cada estado y símbolo, la función de transición tiene exactamente un estado. Por lo tanto, está claro que todos los lenguajes formales que pueden ser reconocidos por un DFA pueden serlo por una NFA.
Por el contrario, para cada NFA, hay un DFA tal que reconoce el mismo lenguaje formal. El DFA se puede construir usando la construcción de powerset .
Este resultado muestra que los NFA, a pesar de su flexibilidad adicional, no pueden reconocer idiomas 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 la NFA tiene n estados, la DFA resultante puede tener hasta estados, lo que a veces hace que la construcción no sea práctica para grandes NFA.
NFA con movimientos ε
El autómata finito no determinista con movimientos ε (NFA-ε) es una generalización adicional a NFA. Este autómata sustituye la función de transición por la que permite la cadena vacía ε como posible entrada. Las transiciones sin consumir un símbolo de entrada se denominan transiciones ε. En los diagramas de estado, generalmente se etiquetan con la letra griega ε. Las transiciones ε proporcionan una forma conveniente de modelar los 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) debería ser q o q ', entonces podemos agregar una transición ε entre estos dos estados, poniendo así el autómata en ambos estados simultáneamente.
Definicion formal
Un NFA-ε está representado formalmente por una tupla de 5 ,, que consiste en
- un conjunto finito de estados
- un conjunto finito de símbolos de entrada llamado alfabeto
- una función de transición
- un estado inicial (o de inicio )
- un conjunto de estados distinguidos como estados de aceptación (o finales ) .
Aquí, denota el conjunto de poder de y ε denota una cadena vacía.
ε-cierre de un estado o conjunto de estados
Por un estado , dejar denotar el conjunto de estados que son alcanzables desde siguiendo ε-transiciones en la función de transición , es decir, si hay una secuencia de estados tal que
- ,
- para cada , y
- .
se conoce como el ε-cierre de.
ε-cierre también se define para un conjunto de estados. El ε-cierre de un conjunto de estados,, de una NFA se define como el conjunto de estados alcanzables desde cualquier estado en siguientes transiciones ε. Formalmente, para, definir .
Aceptando estados
Dejar ser una cadena sobre el alfabeto . El autómata acepta la cuerda si una secuencia de estados, , existe en con las siguientes condiciones:
- dónde para cada , y
- .
En palabras, la primera condición dice que la máquina comienza en el estado que se puede alcanzar desde el estado de inicio. a través de ε-transiciones. La segunda condición dice que después de leer, la máquina realiza una transición de de a , y luego toma cualquier número de transiciones ε de acuerdo con moverse de a . 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. De lo contrario, se dice que el autómata rechaza la cuerda. El conjunto de cuerdasacepta es el idioma reconocido por y este idioma se denota por .
Ejemplo
Dejar ser 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. Tenga en cuenta que 0 apariciones también es un número par de apariciones.
En notación formal, dejemos donde la relación de transición puede ser definido por esta tabla de transición de estado :
Aporte Expresar | 0 | 1 | ε |
---|---|---|---|
S 0 | {} | {} | { S 1 , S 3 } |
S 1 | { S 2 } | { S 1 } | {} |
S 2 | { S 1 } | { S 2 } | {} |
S 3 | { S 3 } | { S 4 } | {} |
S 4 | { S 4 } | { S 3 } | {} |
puede verse como la unión de dos DFA : uno con estados y el otro con estados . El idioma depuede ser descrito por el lenguaje regular dado por esta expresión regular . Definimos usando movimientos ε pero se puede definir sin usar movimientos ε.
Equivalencia a NFA
Para mostrar que NFA-ε es equivalente a NFA, primero tenga en cuenta que NFA es un caso especial de NFA-ε, por lo que queda por mostrar que para cada NFA-ε, existe un NFA equivalente.
Dejar ser un NFA-ε. La NFA es equivalente a , donde para cada y , .
Por tanto, 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 las NFA se cierran bajo un operador ( binario / unario ) si las NFA reconocen los idiomas que se obtienen al aplicar la operación en los idiomas reconocibles de la NFA. Las NFA se cierran en virtud de las siguientes operaciones.
- Unión (ver foto)
- Intersección
- Concatenación
- Negación
- Cierre Kleene
Dado que los NFA son equivalentes a un autómata finito no determinista con movimientos ε (NFA-ε), los cierres anteriores se prueban utilizando las propiedades de cierre de NFA-ε. Las propiedades de cierre anteriores implican que las NFA pueden reconocer idiomas regulares .
Los NFA se pueden construir a partir de cualquier expresión regular utilizando el algoritmo de construcción de Thompson .
Propiedades
La máquina se inicia en el estado inicial especificado y lee una cadena de símbolos de su alfabeto . El autómata usa la función de transición de estado Δ para determinar el siguiente estado usando el estado actual, y el símbolo que acaba de leer o la cadena vacía. Sin embargo, "el siguiente estado de un NFA depende no sólo del evento de entrada actual, sino también de un número arbitrario de eventos de entrada posteriores. Hasta que ocurran estos eventos posteriores, no es posible determinar en qué estado se encuentra la máquina". [8] Si, cuando el autómata ha terminado de leer, está en un estado de aceptación, se dice que la NFA acepta la cadena, de lo contrario se dice que la rechaza.
El conjunto de todas las cadenas aceptadas por una NFA es el idioma que acepta la NFA. Este idioma es un idioma regular .
Para cada NFA se puede encontrar un autómata finito determinista (DFA) que acepta 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 del conjunto de potencias , lo que puede conducir a un aumento exponencial en el número de estados necesarios. Para obtener una prueba formal de la construcción del conjunto de alimentación, consulte el artículo de construcción del conjunto de alimentación .
Implementación
Hay muchas formas de implementar una NFA:
- Convierta al DFA equivalente. En algunos casos, esto puede causar una explosión exponencial en el número de estados. [9]
- Mantenga una estructura de datos establecida de todos los estados en los que podría estar actualmente el NFA. 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 los estados siguientes; si se permiten movimientos ε, incluya todos los estados alcanzables por dicho movimiento (ε-cierre). Cada paso requiere como máximo s 2 cálculos, donde s es el número de estados del NFA. Sobre 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 el tiempo O (ns 2 ), [7] : 153 y el espacio O ( s ).
- Crea varias copias. Para cada decisión de n vías, la NFA crea hastacopias de la máquina. Cada uno entrará en un estado separado. Si, al consumir el último símbolo de entrada, al menos una copia de la NFA está en el estado de aceptación, la NFA aceptará. (Esto también requiere almacenamiento lineal con respecto al número de estados NFA, ya que puede haber una máquina para cada estado NFA).
- Propague los tokens explícitamente a través de la estructura de transición de la NFA y haga coincidir cada vez que un token alcance el estado final. Esto a veces es útil cuando la NFA debe codificar un 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 de objetos, eche un vistazo a Tracematches. [10] )
Aplicación de NFA
Los NFA y DFA son equivalentes en el sentido de que si un idioma es reconocido por un NFA, también lo es por un DFA y viceversa. El establecimiento de tal equivalencia es importante y útil. Es útil porque construir un NFA para reconocer un idioma dado es a veces mucho más fácil que construir un DFA para ese idioma. Es importante porque los NFA pueden usarse 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 las propiedades de cierre de los lenguajes normales utilizando NFA que DFA.
Ver también
- Autómata finito determinista
- Autómata finito no determinista bidireccional
- Autómata de empuje
- Máquina de Turing no determinista
Notas
- ↑ Martin, John (2010). Introducción a los lenguajes y la teoría de la computación . McGraw Hill. pag. 108. ISBN 978-0071289429.
- ^ Rabin, MO; Scott, D. (abril de 1959). "Autómatas finitos y sus problemas de decisión". Revista de investigación y desarrollo de IBM . 3 (2): 114-125. doi : 10.1147 / rd.32.0114 .
- ^ Una secuencia de elección puede conducir a un "callejón sin salida" donde no se aplica ninguna transición para el símbolo de entrada actual; en este caso, se considera infructuoso.
- ^ a b c John E. Hopcroft y Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Lectura / MA: Addison-Wesley. ISBN 0-201-02988-X.
- ^ a b Alfred V. Aho y John E. Hopcroft y Jeffrey D. Ullman (1974). El diseño y análisis de algoritmos informáticos . Lectura / MA: Addison-Wesley. ISBN 0-201-00029-6.
- ^ a b Michael Sipser (1997). Introducción a la Teoría de la Computación . Boston / MA: PWS Publishing Co. ISBN 0-534-94728-X.
- ^ a b c John E. Hopcroft y Rajeev Motwani y Jeffrey D. Ullman (2003). Introducción a la teoría, los lenguajes y la computación de los autómatas (PDF) . Upper Saddle River / Nueva Jersey: Addison Wesley. ISBN 0-201-44124-1.
- ^ FOLDOC Diccionario en línea gratuito de informática, máquina de estados finitos
- ^ http://cseweb.ucsd.edu/~ccalabro/essays/fsa.pdf
- ^ 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 la 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.
Referencias
- MO Rabin y D. Scott, "Autómatas finitos y sus problemas de decisión", IBM Journal of Research and Development , 3 : 2 (1959) pp. 115-125.
- Michael Sipser, Introducción a la teoría de la computación . PWS, Boston. 1997. ISBN 0-534-94728-X . (ver sección 1.2: No determinismo, págs. 47–63.)
- John E. Hopcroft y Jeffrey D. Ullman, Introducción a la teoría, los lenguajes y la computación de los autómatas , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X . (Ver capítulo 2.)