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: