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

Un NFA está representado formalmente por una tupla de 5 , , que consta de

Aquí, denota el conjunto potencia de .

NFA para (0|1) *  1 (0|1) 3 .
Un DFA para ese idioma tiene al menos 16 estados.
El diagrama de estado para M . No es determinista ya que en el estado p leer un 1 puede conducir a poq .
Todas las ejecuciones posibles de M en la cadena de entrada "10".
Todas las ejecuciones posibles de M en la cadena de entrada "1011".
Etiqueta de arco: símbolo de entrada, etiqueta de nodo : estado, verde : estado de inicio, rojo : estado(s) de aceptación.
El diagrama de estado para M
NFA compuesto aceptando la unión de las lenguas de unos NFA 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 hasta el 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 coloreado a la derecha); a partir de ahí, estado fse puede alcanzar mediante otra transición ε. Debido a las transiciones ε, el NFA compuesto es propiamente no determinista incluso si tanto N ( s ) como N ( t ) fueran DFA; viceversa, construir un DFA para el lenguaje de unión (incluso de dos DFA) es mucho más complicado.