Conversión de expresiones regulares a autómatas finitos

Como las expresiones regulares se pueden construir a partir de autómatas finitos utilizando el método de eliminación de estados, el método inverso, el método de descomposición de estados, se puede utilizar para construir autómatas finitos a partir de las expresiones regulares dadas.

Nota: este método construirá NFA (con o sin transiciones ε, según la expresión) para la expresión regular dada, que se puede convertir a DFA mediante la conversión de NFA a DFA .

Método de descomposición de estados

Teorema: Todo lenguaje definido por una expresión regular también está definido por un autómata finito. 

Prueba: Supongamos que L = L(R) para una expresión regular R. Probamos que L = L(M) para algún ε-NFA M con:

1) Exactamente un estado de aceptación.

2) No hay bordes entrantes en el estado inicial.

3) Sin bordes salientes en el estado de aceptación.

La prueba se realiza por inducción estructural en R siguiendo los pasos a continuación:

Paso 1: Cree un estado inicial, digamos q ₁ , y un estado final, digamos q ₂ . Etiquete la transición q ₁ a q ₂ como la expresión regular dada, R, como en la figura 1. Pero, si R es (Q) ^* , el cierre de Kleene de otra expresión regular Q, entonces cree un solo estado inicial, que también será el estado final, como en la figura 2.

 Paso 2: Repita las siguientes reglas (método de descomposición de estados) considerando primero el operador de expresión regular de menor precedencia hasta que no quede ningún operador en la expresión. La precedencia de operadores en expresiones regulares se define como Unión < Concatenación < Cierre de Kleene.

El operador de unión (+) se puede eliminar introduciendo bordes paralelos entre los dos estados de la siguiente manera.

El operador de concatenación (‘.’ o ningún operador en absoluto ) se puede eliminar introduciendo un nuevo estado entre los estados de la siguiente manera.

El cierre de Kleene (*) se puede eliminar mediante la introducción de bucles automáticos en los estados según las siguientes condiciones:

1. Si solo hay un borde saliente en el estado más a la izquierda, es decir, A en la transición A -> B, introduzca el bucle automático en el estado A y etiquete el borde A a B como una transición ε, como se muestra en la Fig. 5.
 

2. De lo contrario, si solo hay un borde entrante en el estado más a la derecha, es decir, B en la transición A -> B, entonces introduzca el bucle automático en el estado B y etiquete el borde A a B como una transición ε, como se muestra en Figura 6.

3. De lo contrario, introduzca un nuevo estado entre dos estados que tengan autobucle etiquetado como expresión. El nuevo estado tendrá transiciones ε con los estados anteriores de la siguiente manera, como se muestra en la Fig. 7.

Ejemplo:

Construya autómatas finitos para la expresión regular, R = (ab + ba) ^*

Solución: 

Paso 1: Como la expresión dada, R, tiene la forma (Q) ^* , crearemos un solo estado inicial que también será el estado final, con el autobucle etiquetado (ab + ba), como se muestra en la Fig. 8. (Consulte la figura 2 anterior)

 Paso 2: A. Como el operador de menor precedencia en la expresión es una unión (+). Así que introduciremos aristas paralelas (bucles automáticos paralelos aquí) para ‘ab’ y ‘ba’, como se muestra en la Fig. 9.
 

B. Ahora tenemos dos etiquetas con operadores de concatenación (ningún operador mencionado entre dos variables es concatenación), por lo que los eliminamos uno por uno introduciendo nuevos estados, q ₁ y q ₂ como se muestra en la Fig. 10 y la Fig. 11. (Consulte la Fig. 4 arriba)

Paso 3: Como no quedan operadores, podemos decir que la figura 11 es el autómata finito requerido (NFA).