Automata Finito No Determinista
Es el autómata finito que tiene transiciones vacías o que por cada símbolo desde un estado de origen se llega a más de un estado destino, es decir, es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado, tal que para un símbolo del alfabeto, existe más de una transición posible.
 |
| Ejemplo 1 |
La definición formal de AFND se basa en la consideración de que a menudo según los algoritmos de transformación de expresiones y gramáticas regulares a AF terminan obteniéndose autómatas con transiciones múltiples para un mismo símbolo o transiciones vacías. Independientemente que sean indeseables, sobre todo para la implementación material, fundamentalmente mecánica, de los autómatas finitos, son imprescindibles durante la modelación de analizadores lexicográficos de los elementos gramaticales de los lenguajes de programación, llamados tokens, como literales numéricos, identificadores, cadenas de texto, operadores, etc.
Los AFND son definiciones no tan deseables dentro de los lenguajes regulares porque dificultan su implementación tanto mecánica como informática; aunque en la mayoría de las transformaciones a lo interno de los LR (expresiones regulares a AF, gramáticas regulares a AF) conducen a AFND. Los AFND, por tanto, son imprescindibles en el análisis lexicográfico y el diseño de los lenguajes de programación.
Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos:
- Que existan transiciones del tipo δ(q, a)=q1 y δ(q, a)=q2 siendo q1≠q2 ;
- Que existan transiciones del tipo, δ(q, ε) siendo un estado no-final, o bien un estado final pero con transiciones hacia otros estados.
Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFNDε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada.
 |
| Ejemplo 2 |
DEFINICIÓN: Sea un autómata finito definido por la quíntupla A=(Q,Σ,q0 ,δ,F) donde:
Q: es el conjunto finito de estados
Σ: es un alfabeto finito
q0 ∈ Q: es el estado inicial
F⊆Q: es un conjunto de estados finales o de aceptación
δ: Qx(∑∪{ε})→ P(Q): cuando contiene transiciones vacías
δ: Qx∑→ P(Q) ó δ: {qi,x,qj | qi 〖,q〗j ∈Q;x∈∑} - (del estado qi mediante el terminal x se va a qj ), es la función de transición.
Esto significa que los autómatas finitos deterministas son un caso particular de los no deterministas, puesto que Q pertenece al conjunto P (Q).
Se dice que es un autómata finito no determinista (AFND) si y sólo si existen en δ al menos una de las siguientes transiciones:
 |
| Ejemplo 3 |
 |
| Cuadro de Estados y Transiciones del Ejemplo 3 |
AFND`s pueden presentarse mediante tablas de transiciones.
En las filas los estados.
Si el estado es final lo antecederá un *.
Si el estado es inicial lo marcaremos con una →
En las columnas se pondrán los símbolos del alfabeto de entrada y se añadirá una columna adicional para ε .
En la intersección (celdas de la matriz) se indicarán las transiciones
 |
| TABLA COMPLEMENTARIA DEL EJEMPLO 3 |
Características.
El resultado de la función de transición puede ser el conjunto vacío (pares estado/símbolo terminal para las que el autómata no puede transitar). Se suelen omitir estas entradas en las tablas de transiciones δ(q0,ε),…
El autómata puede transitar sin leer ningún símbolo de entrada: δ(q1,ε)={q0,q1 }
El no determinismo del autómata proviene del hecho de que en cada momento (para cada símbolo de entrada y estado) pueden existir varias posibilidades de transición (o ninguna).
Función de transición extendida
La función de transición extendida se define de la siguiente manera:δ*:Qx∑*→P(Q)
La función de transición extendida para los AFNDε : δ* (q,ε)= cierreε (q)
cierreε: es el conjunto de estados a los que podemos llegar desde un estado dado con 0 o más transiciones, es decir, sin procesar la entrada. cierreε:Q→P(Q)
Recursivamente: δ* (q,wa)=Umj=1cierreε(rj)
Lenguaje reconocido por un AFND
Intuitivamente, un AFND acepta todas las palabras para las que puede transitar desde el estado inicial a un estado final.
Lenguaje reconocido: sea un AFND A = (Q,∑,δ,q0,F) El lenguaje reconocido por A está formado por el conjunto de palabras que pueden hacer transitar el autómata desde el estado hasta un estado final (A)={x|x∈∑* y δ* (q0,x)∩F≠∅}.
Significa que el lenguaje aceptado por un AFND estará constituido por todas las cadenas formadas con símbolos del alfabeto de entrada, que, partiendo desde el estado inicial, el autómata quedará posicionado en un estado que pertenezca al conjunto de estados finales de aceptación.
 |
| Ejemplo 4 |
La interpretación que se suele hacer en el cómputo de un AFND es que el autómata puede estar en varios estados a la vez, generándose una ramificación de las configuraciones existentes en un momento dado. Otra interpretación puede ser imaginar que la máquina "adivina" a qué estado debe ir, eligiendo una transición entre varias posibles. Note finalmente que en un autómata finito no determinista podemos aceptar la existencia de más de un nodo inicial, relajando aún más la definición original.
Finalmente, dejamos un video donde se explican estos conceptos.
- Anónimo. (ND). AUTÓMATA FINITO NO DETERMINISTA. Enero 16, 2021, de Teoria de Autómatas Wiki Sitio web: https://automatas.fandom.com/es/wiki/AUT%C3%93MATA_FINITO_NO_DETERMINISTA
- Ojeda, L.. (Mayo, 2007). AUTÓMATAS DETERMINISTAS Y NO DETERMINISTAS. Compufacil, 13, pp 18-20.
Escribió: Juan Pablo Jiménez Macias
Editó: Rodrigo R. Rubio Haro.