V tem razdelku bomo razpravljali o metodi pretvorbe NFA v enakovreden DFA. V NFA, ko je določen vnos podan trenutnemu stanju, stroj preide v več stanj. Lahko ima nič, eno ali več kot eno potezo na danem vhodnem simbolu. Po drugi strani pa v DFA, ko je določen vnos podan trenutnemu stanju, stroj preide v samo eno stanje. DFA ima samo eno potezo na danem vhodnem simbolu.
Naj je M = (Q, ∑, δ, q0, F) NFA, ki sprejema jezik L(M). Obstajati mora enakovredni DFA, označen z M' = (Q', ∑', q0', δ', F'), tako da je L(M) = L(M').
Koraki za pretvorbo NFA v DFA:
Korak 1: Na začetku Q' = ϕ
2. korak: Q' dodajte q0 NFA. Nato poiščite prehode iz tega začetnega stanja.
3. korak: V Q' poiščite možen nabor stanj za vsak vhodni simbol. Če ta niz stanj ni v Q', ga dodajte v Q'.
testiranje in vrste programske opreme
4. korak: V DFA bodo končna stanja vsa stanja, ki vsebujejo F (končna stanja NFA)
Primer 1:
Pretvorite podani NFA v DFA.
rešitev: Za dani prehodni diagram bomo najprej izdelali prehodno tabelo.
Država | 0 | 1 |
---|---|---|
→q0 | q0 | q1 |
q1 | {q1, q2} | q1 |
*q2 | q2 | {q1, q2} |
Zdaj bomo dobili prehod δ' za stanje q0.
cm do stopal in palcev
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
Prehod δ' za stanje q1 dobimo kot:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
Prehod δ' za stanje q2 dobimo kot:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Zdaj bomo dobili δ' prehod na [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]
Tudi stanje [q1, q2] je končno stanje, ker vsebuje končno stanje q2. Prehodna tabela za konstruirano DFA bo:
bash if stanje
Država | 0 | 1 |
---|---|---|
→[q0] | [q0] | [q1] |
[q1] | [q1, q2] | [q1] |
*[q2] | [q2] | [q1, q2] |
*[q1, q2] | [q1, q2] | [q1, q2] |
Diagram prehoda bo:
Stanje q2 lahko odpravimo, ker je q2 nedosegljivo stanje.
Primer 2:
Pretvorite podani NFA v DFA.
rešitev: Za dani prehodni diagram bomo najprej izdelali prehodno tabelo.
python konstruktor
Država | 0 | 1 |
---|---|---|
→q0 | {q0, q1} | {q1} |
*q1 | ϕ | {q0, q1} |
Zdaj bomo dobili prehod δ' za stanje q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1]
Prehod δ' za stanje q1 dobimo kot:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Zdaj bomo dobili δ' prehod na [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1]
Podobno,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1]
Kot v danem NFA je q1 končno stanje, potem v DFA, kjer koli obstaja q1, to stanje postane končno stanje. Zato sta v DFA končni stanji [q1] in [q0, q1]. Zato je množica končnih stanj F = {[q1], [q0, q1]}.
vrste računalnika
Prehodna tabela za konstruirano DFA bo:
Država | 0 | 1 |
---|---|---|
→[q0] | [q0, q1] | [q1] |
*[q1] | ϕ | [q0, q1] |
*[q0, q1] | [q0, q1] | [q0, q1] |
Diagram prehoda bo:
Tudi imena držav DFA lahko spremenimo.
Recimo
A = [q0] B = [q1] C = [q0, q1]
S temi novimi imeni bo DFA naslednji: