Konwersja NDFA do DFA

Stwierdzenie problemu

Pozwolić X = (Qx, ∑, δx, q0, Fx)być NDFA, który akceptuje język L (X). Musimy zaprojektować równoważny DFAY = (Qy, ∑, δy, q0, Fy) takie że L(Y) = L(X). Poniższa procedura konwertuje NDFA na jego odpowiednik DFA -

Algorytm

Input - NDFA

Output - Odpowiednik DFA

Step 1 - Utwórz tabelę stanów z podanego NDFA.

Step 2 - Utwórz pustą tabelę stanów pod możliwymi alfabetami wejściowymi dla równoważnego DFA.

Step 3 - Oznacz stan początkowy DFA przez q0 (tak samo jak w przypadku NDFA).

Step 4- Znajdź kombinację stanów {Q 0 , Q 1 , ..., Q n } dla każdego możliwego alfabetu wejściowego.

Step 5 - Za każdym razem, gdy generujemy nowy stan DFA pod kolumnami alfabetu wejściowego, musimy ponownie zastosować krok 4, w przeciwnym razie przejść do kroku 6.

Step 6 - Stany, które zawierają dowolny ze stanów końcowych NDFA, są stanami końcowymi równoważnego DFA.

Przykład

Rozważmy NDFA pokazane na poniższym rysunku.

q δ (q, 0) δ (q, 1)
za {a, b, c, d, e} {d, e}
b {do} {mi}
do {b}
re {mi}
mi

Korzystając z powyższego algorytmu, znajdujemy jego odpowiednik DFA. Tabela stanów DFA jest pokazana poniżej.

q δ (q, 0) δ (q, 1)
[za] [a, b, c, d, e] [d, e]
[a, b, c, d, e] [a, b, c, d, e] [b, d, e]
[d, e] [mi]
[b, d, e] [c, e] [mi]
[mi]
[c, e] [b]
[b] [do] [mi]
[do] [b]

Schemat stanu DFA jest następujący -