Autómata finito no determinista
Estamos acostumbrados a dibujar un autómata finito no determinista, representando los estados con círculos, indicando el estado inicial con una flecha de entrada, los estados de aceptación con un doble círculo o una flecha de salida, y la transición del estado q al estado q' leyendo la letra α por una flecha que va de q a q' y está etiquetada con α.
Un autómata finito no determinista A es un triplete (Vt, Q, T) donde
- Vt es el vocabulario del autómata;
- Q es el conjunto finito de estados del autómata;
- T: Q × Vt → Q, es una aplicación parcial llamada función de transición del autómata.
Tenga en cuenta que un autómata determinista es un caso particular de un autómata no determinista que asocia con cualquier elemento de Q × Vt una parte de Q que tiene cero o un elemento (exactamente uno si es un autómata completo). De un autómata determinista podemos decir que está incompleto si se puede bloquear, es decir, si existe un estado q y una letra a tal que T (q, a) = ∅. Si está completo, tenemos la siguiente propiedad:
Sea A = (Vt, Q, T) un autómata finito no determinista completo. Entonces, para cualquier palabra u ∈ V∗t y cualquier estado q ∈ Q, existe un estado (no siempre único) q '∈ Q tal que q (u) → Aq'.
Sin embargo, lo no determinista tiene una consecuencia esencial: puede haber varias derivaciones resultantes del estado inicial i que leen una palabra dada w, algunas de las cuales pueden bloquearse y otras no, y en el último caso algunas pueden terminar en el estado de aceptación y otros no. La aceptación tiene lugar si hay al menos un cálculo exitoso. Si todos los cálculos fallan, no habrá otra forma de averiguarlo que explorarlos todos antes de saber que la palabra w no coincide. Por tanto, la noción correcta no es la de cálculo, sino la de un árbol de cálculo asociado a una palabra leída por el autómata:
Dado un autómata finito no determinista A, el árbol de derivación con raíz q ∈ Q generado al leer la palabra u es un árbol doblemente etiquetado definido por inducción en u:
Si u = ε, entonces el árbol se reduce a su raíz q;
Si u = av, la raíz q tiene transiciones salientes etiquetadas por a ∈ Vt a diferentes árboles computacionales generados por la lectura de v y cuyas raíces están etiquetadas por los estados de T (q, a).
Un árbol de derivación se construye como en el caso de un autómata determinista. En el caso de un autómata finito no determinista, no es lineal y puede presentar varias ramas que darán varias derivaciones que conduzcan o no al reconocimiento de la palabra.
Una palabra u es reconocida por un autómata no determinista A si una de las hojas de su árbol de cálculo está etiquetada con un estado de aceptación.
No determinismo y palabras reconocidas
Consideramos el siguiente autómata finito no determinista A = ({a, b}, {1, 2, 3}, ∆, {1}, {1}):
¿El autómata A acepta la palabra baabab?
Ninguna hoja corresponde a un estado final, tenga en cuenta que todas las hojas terminan en el pozo.
Al igual que el autómata determinista, es posible construir las palabras reconocidas por el autómata mirando las líneas de entrada y las columnas de salida. Las palabras de longitudes n se construyen luego elevando la matriz de transición a la potencia de n.
ES 
FR 
EN