Conversión de NDFA a DFA

Planteamiento del problema

Dejar X = (Q_x, ∑, δ_x, q₀, F_x)Ser un NDFA que acepte el lenguaje L (X). Tenemos que diseñar un DFA equivalenteY = (Q_y, ∑, δ_y, q₀, F_y) tal que L(Y) = L(X). El siguiente procedimiento convierte el NDFA en su DFA equivalente:

Algoritmo

Input - Un NDFA

Output - Un DFA equivalente

Step 1 - Crear tabla de estado a partir del NDFA dado.

Step 2 - Cree una tabla de estado en blanco bajo posibles alfabetos de entrada para el DFA equivalente.

Step 3 - Marque el estado de inicio del DFA con q0 (Igual que el NDFA).

Step 4- Descubra la combinación de estados {Q ₀ , Q ₁ , ..., Q _n } para cada posible alfabeto de entrada.

Step 5 - Cada vez que generamos un nuevo estado DFA bajo las columnas del alfabeto de entrada, tenemos que aplicar el paso 4 nuevamente; de ​​lo contrario, vaya al paso 6.

Step 6 - Los estados que contienen cualquiera de los estados finales del NDFA son los estados finales del DFA equivalente.

Ejemplo

Consideremos el NDFA que se muestra en la figura siguiente.

q	δ (q, 0)	δ (q, 1)
un	{a B C D e}	{Delaware}
segundo	{C}	{mi}
C	∅	{segundo}
re	{mi}	∅
mi	∅	∅

Usando el algoritmo anterior, encontramos su DFA equivalente. La tabla de estado del DFA se muestra a continuación.

q	δ (q, 0)	δ (q, 1)
[un]	[a B C D e]	[Delaware]
[a B C D e]	[a B C D e]	[b, d, e]
[Delaware]	[mi]	∅
[b, d, e]	[c, e]	[mi]
[mi]	∅	∅
[c, e]	∅	[segundo]
[segundo]	[C]	[mi]
[C]	∅	[segundo]

El diagrama de estado del DFA es el siguiente: