Conversão NDFA para DFA

Declaração do Problema

Deixei X = (Q_x, ∑, δ_x, q₀, F_x)ser um NDFA que aceita a linguagem L (X). Temos que projetar um DFA equivalenteY = (Q_y, ∑, δ_y, q₀, F_y) de tal modo que L(Y) = L(X). O procedimento a seguir converte o NDFA em seu DFA equivalente -

Algoritmo

Input - Um NDFA

Output - Um DFA equivalente

Step 1 - Crie uma tabela de estados a partir do NDFA fornecido.

Step 2 - Crie uma tabela de estado em branco em possíveis alfabetos de entrada para o DFA equivalente.

Step 3 - Marque o estado inicial do DFA por q0 (igual ao NDFA).

Step 4- Descubra a combinação dos estados {Q ₀ , Q ₁ , ..., Q _n } para cada alfabeto de entrada possível.

Step 5 - Cada vez que geramos um novo estado DFA nas colunas do alfabeto de entrada, temos que aplicar a etapa 4 novamente, caso contrário, vá para a etapa 6.

Step 6 - Os estados que contêm qualquer um dos estados finais do NDFA são os estados finais do DFA equivalente.

Exemplo

Vamos considerar o NDFA mostrado na figura abaixo.

q	δ (q, 0)	δ (q, 1)
uma	{a, b, c, d, e}	{d, e}
b	{c}	{e}
c	∅	{b}
d	{e}	∅
e	∅	∅

Usando o algoritmo acima, encontramos seu DFA equivalente. A tabela de estado do DFA é mostrada a seguir.

q	δ (q, 0)	δ (q, 1)
[uma]	[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]

O diagrama de estado do DFA é o seguinte -