In diesem Abschnitt besprechen wir die Methode zur Umrechnung von NFA in den entsprechenden DFA. Wenn in NFA eine bestimmte Eingabe für den aktuellen Status erfolgt, wechselt die Maschine in mehrere Status. Es kann null, eine oder mehr als eine Bewegung auf einem bestimmten Eingabesymbol haben. Wenn andererseits in DFA eine bestimmte Eingabe für den aktuellen Status erfolgt, wechselt die Maschine nur in einen Status. DFA hat nur einen Zug auf einem bestimmten Eingabesymbol.
Sei M = (Q, ∑, δ, q0, F) ein NFA, der die Sprache L(M) akzeptiert. Es sollte einen äquivalenten DFA geben, der durch M' = (Q', ∑', q0', δ', F') bezeichnet wird, so dass L(M) = L(M').
Schritte zur Konvertierung von NFA in DFA:
Schritt 1: Zunächst ist Q' = ϕ
Schritt 2: Addiere q0 von NFA zu Q'. Finden Sie dann die Übergänge von diesem Startzustand.
Schritt 3: Finden Sie in Q' die möglichen Zustände für jedes Eingabesymbol. Wenn diese Menge von Zuständen nicht in Q‘ ist, dann füge sie zu Q‘ hinzu.
Schritt 4: In DFA sind alle Staaten, die F enthalten (Endzustände von NFA), der Endzustand.
Beispiel 1:
Konvertieren Sie den angegebenen NFA in DFA.
Lösung: Für das gegebene Übergangsdiagramm erstellen wir zunächst die Übergangstabelle.
| Zustand | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Jetzt erhalten wir den δ'-Übergang für den Zustand q0.
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
Der δ'-Übergang für den Zustand q1 ergibt sich zu:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
Der δ'-Übergang für den Zustand q2 ergibt sich zu:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Jetzt erhalten wir den δ'-Übergang auf [q1, q2].
δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0) = {q1, q2} ∪ {q2} = [q1, q2] δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1) = {q1} ∪ {q1, q2} = {q1, q2} = [q1, q2] Der Zustand [q1, q2] ist ebenfalls der Endzustand, da er einen Endzustand q2 enthält. Die Übergangstabelle für den erstellten DFA lautet:
| Zustand | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Das Übergangsdiagramm sieht wie folgt aus:
Der Zustand q2 kann eliminiert werden, da q2 ein nicht erreichbarer Zustand ist.
sind Musterbeispiele
Beispiel 2:
Konvertieren Sie den angegebenen NFA in DFA.
Lösung: Für das gegebene Übergangsdiagramm erstellen wir zunächst die Übergangstabelle.
| Zustand | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Jetzt erhalten wir den δ'-Übergang für den Zustand q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] Der δ'-Übergang für den Zustand q1 ergibt sich zu:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Jetzt erhalten wir den δ'-Übergang auf [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] Ähnlich,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Wie in der gegebenen NFA ist q1 ein Endzustand, und in der DFA wird dieser Zustand überall dort, wo q1 existiert, zu einem Endzustand. Daher sind im DFA die Endzustände [q1] und [q0, q1]. Daher Menge der Endzustände F = {[q1], [q0, q1]}.
Die Übergangstabelle für den erstellten DFA lautet:
| Zustand | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Das Übergangsdiagramm sieht wie folgt aus:
Sogar wir können den Namen der DFA-Bundesstaaten ändern.
Vermuten
A = [q0] B = [q1] C = [q0, q1]
Mit diesen neuen Namen wird das DFA wie folgt lauten:
