Los autómatas finitos no deterministas (NFA) son autómatas finitos que tienen cero, uno o más de un movimiento desde un estado dado en un símbolo de entrada dado. Epsilon NFA es el NFA que contiene movimiento(s) epsilon/movimiento(s) nulo(s). Para eliminar el movimiento epsilon/movimiento nulo de epsilon-NFA y convertirlo en NFA, seguimos los pasos que se mencionan a continuación.
Paso 1:
considere los dos vértices que tienen el movimiento épsilon. Aquí, en la Fig . 1 , tenemos el vértice v1 y el vértice v2 con épsilon moviéndose de v1 a v2.
Paso 2:
ahora encuentre todos los movimientos a cualquier otro vértice que comience desde el vértice v2 (aparte del movimiento épsilon que está considerando).
Después de encontrar los movimientos, duplique todos los movimientos que comienzan desde el vértice v2, con la misma entrada para comenzar desde el vértice v1 y elimine el movimiento épsilon del vértice v1 al vértice v2.
Paso 3:
vea si el vértice v1 es un estado de inicio o no. Si el vértice v1 es un estado de inicio, también haremos que el vértice v2 sea un estado de inicio. Si el vértice v1 no es un estado de inicio, entonces no habrá ningún cambio.
Paso 4:
vea si el vértice v2 es un estado final o no.
Si el vértice v2 es un estado final, entonces también haremos que el vértice v1 sea un estado final.
Si el vértice v2 no es un estado final, entonces no habrá ningún cambio.
Repita los pasos (del paso 1 al paso 4) hasta que todos los movimientos épsilon se eliminen del NFA.
Ahora, para explicar esta conversión, tomemos un ejemplo.
Ejemplo: convertir epsilon-NFA a NFA.
Considere el ejemplo que tiene los estados q0, q1, q2, q3 y q4.
En el ejemplo anterior, tenemos 5 estados denominados q0, q1, q2, q3 y q4. Inicialmente, tenemos q0 como estado inicial y q2 como estado final. Tenemos q1, q3 y q4 como estados intermedios.
La tabla de transición para el NFA anterior es:
| Estados/Entrada | Entrada 0 | Entrada 1 | Épsilon de entrada |
|---|---|---|---|
| q0 | – | q1 | q2 |
| q1 | – | q0 | – |
| q2 | q3 | q4 | – |
| q3 | q2 | – | – |
| q4 | q2 | – | – |
De acuerdo con la tabla de transición anterior,
- el estado q0 al obtener la entrada 1 pasa al estado q1.
- El estado q0 al obtener entrada como un movimiento nulo (es decir, un movimiento épsilon) pasa al estado q2.
- El estado q1 al obtener la entrada 1 pasa al estado q0.
- De manera similar, el estado q2 al obtener la entrada 0 pasa al estado q3, el estado q2 al obtener la entrada 1 pasa al estado q4.
- De manera similar, el estado q3 al obtener la entrada 0 pasa al estado q2.
- De manera similar, el estado q4 al obtener la entrada 0 pasa al estado q2.
Podemos ver que tenemos un movimiento épsilon del estado q0 al estado q2, que debe eliminarse.
Para eliminar el movimiento epsilon del estado q0 al estado q1, seguiremos los pasos que se mencionan a continuación.
Paso 1:
considerando el movimiento épsilon del estado q0 al estado q2. Considere el estado q0 como vértice v1 y el estado q2 como vértice v2.
Paso 2:
ahora encuentra todos los movimientos que comienzan desde el vértice v2 (es decir, el estado q2) .
Después de encontrar los movimientos, duplique todos los movimientos que comienzan desde el vértice v2 (es decir, el estado q2) con la misma entrada para comenzar desde el vértice v1 (es decir, el estado q0) y elimine el movimiento épsilon del vértice v1 (es decir, el estado q0) al vértice v2 ( es decir, estado q2) .
Dado que el estado q2 al obtener la entrada 0 pasa al estado q3.
Por lo tanto, al duplicar el movimiento, tendremos el estado q0 al obtener la entrada 0 también para ir al estado q3.
Del mismo modo, el estado q2 al obtener la entrada 1 pasa al estado q4.
Por lo tanto, al duplicar el movimiento, tendremos el estado q0 al obtener la entrada 1 también para ir al estado q4.
Entonces, NFA después de duplicar los movimientos es:
Paso 3:
Dado que el vértice v1 (es decir, el estado q0) es un estado inicial. Por lo tanto, también haremos el vértice v2 (es decir, el estado q2) como estado inicial.
Tenga en cuenta que el estado q2 también permanecerá como un estado final como lo teníamos inicialmente.
NFA después de hacer el estado q2 también como estado de inicio es:
Paso 4:
Dado que el vértice v2 (es decir, el estado q2) es un estado final. Por lo tanto, también haremos el vértice v1 (es decir, el estado q0) como estado final.
Tenga en cuenta que el estado q0 también permanecerá como un estado inicial como lo teníamos inicialmente.
Después de hacer el estado q0 también como estado final, el NFA resultante es:
La tabla de transición para el NFA resultante anterior es:
| Estados/Entrada | Entrada 0 | Entrada 1 |
|---|---|---|
| q0 | q3 | q1,q4 |
| q1 | – | q0 |
| q2 | q3 | q4 |
| q3 | q2 | – |
| q4 | q2 | – |