Conversión de NDFA a DFA
AREAtutorial » Tutoriales de IngenierÃa » Conversión de NDFA a DFA
Dejar X = (Qx, ∑, δx, q0, Fx) ser un NDFA que acepte el lenguaje L (X). Debemos desarrollar un DFA equivalente Y = (Qy, ∑, δy, q0, Fy) tal que L (Y) = L (X)… El siguiente procedimiento convertirá NDFA en DFA equivalente:
aporte – NDFA
Salida – Equivalente de DFA
Paso 1 – Cree una tabla de estado a partir de un NDFA determinado.
Paso 2 – Cree una tabla de estado vacÃa para posibles alfabetos de entrada para el DFA equivalente.
Paso 3 – Marque el estado inicial del DFA como q0 (igual que NDFA).
Paso 4 – Encuentre una combinación de estados {Q0, Q1,…, Qn} para cada posible alfabeto de entrada.
Paso 5 – Cada vez que creamos un nuevo estado DFA bajo las columnas del alfabeto de entrada, debemos aplicar el paso 4 nuevamente; de ​​lo contrario, ir al paso 6.
PASO 6 – Los estados que contienen cualquiera de los estados finales del NDFA son los estados finales del DFA equivalente.
Echemos un vistazo al NDFA que se muestra en la siguiente figura.
| q | δ (q, 0) | δ (d, 1) |
|---|---|---|
| y | {a B C D e} | {d, e} |
| B | {C} | {mi} |
| C | ∅ | {B} |
| D | {mi} | ∅ |
| mi | ∅ | ∅ |
Usando el algoritmo descrito anteriormente, encontramos su equivalente DFA. La tabla de estado de DFA se muestra a continuación.
| q | δ (q, 0) | δ (d, 1) |
|---|---|---|
| [a] | [a,b,c,d,e] | [d,e] |
| [a,b,c,d,e] | [a,b,c,d,e] | [b,d,e] |
| [d,e] | [e] | ∅ |
| [b,d,e] | [c,e] | [e] |
| [e] | ∅ | ∅ |
| [c, e] | ∅ | [b] |
| [b] | [c] | [e] |
| [c] | ∅ | [b] |
El diagrama de estado de DFA es el siguiente:
🚫