Konvertierung von NDFA in DFA
Problemstellung
Lassen X = (Qx, ∑, δx, q0, Fx)sei ein NDFA, der die Sprache L (X) akzeptiert. Wir müssen einen äquivalenten DFA entwerfenY = (Qy, ∑, δy, q0, Fy) so dass L(Y) = L(X). Das folgende Verfahren konvertiert den NDFA in seinen entsprechenden DFA -
Algorithmus
Input - Ein NDFA
Output - Ein gleichwertiger DFA
Step 1 - Erstellen Sie eine Statustabelle aus dem angegebenen NDFA.
Step 2 - Erstellen Sie eine leere Statustabelle unter möglichen Eingabealphabeten für den entsprechenden DFA.
Step 3 - Markieren Sie den Startzustand des DFA mit q0 (wie beim NDFA).
Step 4- Finden Sie die Kombination der Zustände {Q 0 , Q 1 , ..., Q n } für jedes mögliche Eingabealphabet heraus.
Step 5 - Jedes Mal, wenn wir einen neuen DFA-Status unter den Spalten des Eingabealphabets generieren, müssen wir Schritt 4 erneut anwenden, andernfalls fahren Sie mit Schritt 6 fort.
Step 6 - Die Zustände, die einen der Endzustände des NDFA enthalten, sind die Endzustände des entsprechenden DFA.
Beispiel
Betrachten wir den in der folgenden Abbildung gezeigten NDFA.
| q | δ (q, 0) | δ (q, 1) |
|---|---|---|
| ein | {a, b, c, d, e} | {d, e} |
| b | {c} | {e} |
| c | ∅ | {b} |
| d | {e} | ∅ |
| e | ∅ | ∅ |
Unter Verwendung des obigen Algorithmus finden wir seinen äquivalenten DFA. Die Statustabelle des DFA ist unten dargestellt.
| q | δ (q, 0) | δ (q, 1) |
|---|---|---|
| [ein] | [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] |
Das Zustandsdiagramm des DFA lautet wie folgt:
