Autómata finito no determinista generalizado

El autómata finito no determinista generalizado, en forma abreviada AFND generalizado, es un autómata no determinista que en las transiciones no tiene por fuerza solo símbolos del alfabeto, sino que puede tener una expresión regular.

Definición

Necesitaremos el AFND generalizado durante el algoritmo de conversión de un autómata finito en una expresión regular. Un AFND generalizado es, pues, un AFND cuyas transiciones están definidas mediante expresiones regulares. Ejemplo de un AFND generalizado así:

Vemos que, por ejemplo, del estado q₂ sale una transición al estado q_f y está etiquetada con la expresión regular a^∗ b. Otros requisitos del AFND generalizado:

• El estado inicial q₀ debe tener una transición a todos los demás estados. En la figura vemos que del estado q₀ salen transiciones a todos los demás estados.
• En un AFND generalizado existe un único estado final y todos los demás estados tienen una transición a ese estado. Como se ve en la figura, todos los estados tienen una flecha que apunta a q_f.
• El estado inicial no puede coincidir con el estado final. Un AFND generalizado tiene, por tanto, como mínimo dos estados.
• Todos los demás estados, salvo el inicial y el final, deben tener transiciones a todos los demás estados, salvo el inicial y el final. Incluidos los bucles (transición del estado q_i al estado q_i).

Conversión de un AFND corriente en un AFND generalizado

Si tenemos un AFND, la conversión a AFND generalizado es sencilla.

1. Creamos un nuevo estado inicial q_s y una transición ε hacia el estado inicial original.
2. Creamos un nuevo estado final q_f y desde todos los estados finales originales trazamos transiciones ε hacia el estado q_f. Los estados finales originales pasan a ser estados normales.
3. Si en algún sitio existe una transición múltiple (es decir, si del estado q₁ llegamos al estado q₂ tanto con el símbolo 0 como con el símbolo 1), fundimos estas reglas en una sola expresión regular y unimos todos los símbolos originales con el operador de unión (es decir, etiquetamos la flecha con la expresión regular 0 ∣ 1).
4. Si en el autómata falta alguna transición que según la definición debería estar, la creamos y la etiquetamos con la expresión regular ∅. Con eso no cambiamos el lenguaje que acepta el autómata, porque esa transición nunca se realiza.

Este autómata podemos usarlo para convertir un autómata en una expresión regular.