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 -
