Autómata finito no determinista
Un autómata finito no determinista ( NFA ), o una máquina de estado finito 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, en referencia 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 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 movimientos ε , transductores de estado finito , autómatas pushdown , autómatas alternos, autómatas ω y autómatas probabilísticos . Además de los DFA, otros casos especiales conocidos de NFA son los autómatas finitos inequívocos (UFA) y los autómatas finitos autoverificadores (SVFA).
Hay dos formas de describir el comportamiento de un NFA, y ambas son equivalentes. La primera forma hace uso del no determinismo en nombre de una NFA. Para cada símbolo de entrada, el NFA 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 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
En la segunda forma, la NFA consume una cadena de símbolos de entrada, uno por uno. En cada paso, siempre que se apliquen dos o más transiciones, se "clona" a sí mismo en muchas copias apropiadas, 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 se encuentra en estado de aceptación, se acepta la entrada, de lo contrario, se rechaza. [4] : 19–20 [6] : 48 [7] : 56
