In deze sectie bespreken we de methode voor het converteren van NFA naar het equivalente DFA. Wanneer in NFA een specifieke invoer wordt gegeven aan de huidige status, gaat de machine naar meerdere staten. Het kan nul, één of meer dan één zet hebben op een bepaald invoersymbool. Aan de andere kant, in DFA, wanneer een specifieke invoer wordt gegeven aan de huidige status, gaat de machine naar slechts één status. DFA heeft slechts één zet op een bepaald invoersymbool.
Stel dat M = (Q, ∑, δ, q0, F) een NFA is die de taal L(M) accepteert. Er moet een equivalente DFA zijn, aangegeven met M' = (Q', ∑', q0', δ', F'), zodat L(M) = L(M').
Stappen voor het converteren van NFA naar DFA:
Stap 1: Aanvankelijk Q' = ϕ
Stap 2: Voeg q0 NFA toe aan Q'. Zoek vervolgens de overgangen vanuit deze startstatus.
Stap 3: Zoek in Q' de mogelijke reeks toestanden voor elk invoersymbool. Als deze reeks toestanden zich niet in Q' bevindt, voeg deze dan toe aan Q'.
Stap 4: In DFA zijn de eindtoestanden alle staten die F bevatten (eindtoestanden van NFA)
Voorbeeld 1:
Converteer de gegeven NFA naar DFA.
Oplossing: Voor het gegeven transitiediagram gaan we eerst de transitietabel construeren.
| Staat | 0 | 1 |
|---|---|---|
| →q0 | Q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | Q2 | {q1, q2} |
Nu zullen we de δ'-overgang verkrijgen voor toestand q0.
np waar
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
De δ'-overgang voor toestand q1 wordt verkregen als:
10 1 miljoen
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
De δ'-overgang voor toestand q2 wordt verkregen als:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Nu zullen we de δ'-overgang verkrijgen op [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] De toestand [q1, q2] is tevens de eindtoestand omdat deze een eindtoestand q2 bevat. De overgangstabel voor de geconstrueerde DFA zal er als volgt uitzien:
| Staat | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Het transitiediagram ziet er als volgt uit:
De toestand q2 kan worden geëlimineerd omdat q2 een onbereikbare toestand is.
Voorbeeld 2:
Converteer de gegeven NFA naar DFA.
Oplossing: Voor het gegeven transitiediagram gaan we eerst de transitietabel construeren.
| Staat | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Nu zullen we de δ'-overgang verkrijgen voor toestand q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] De δ'-overgang voor toestand q1 wordt verkregen als:
arp-a-opdracht
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Nu zullen we de δ'-overgang verkrijgen op [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] Op dezelfde manier,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Net als in de gegeven NFA is q1 een eindtoestand, en in DFA, waar dan ook, q1 bestaat, wordt die toestand een eindtoestand. Daarom zijn in de DFA de eindtoestanden [q1] en [q0, q1]. Daarom set eindtoestanden F = {[q1], [q0, q1]}.
De overgangstabel voor de geconstrueerde DFA zal er als volgt uitzien:
| Staat | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Het transitiediagram ziet er als volgt uit:
Zelfs wij kunnen de naam van de staten van DFA veranderen.
Veronderstellen
A = [q0] B = [q1] C = [q0, q1]
Met deze nieuwe namen zal de DFA er als volgt uitzien:
