Tässä osiossa keskustelemme menetelmästä, jolla NFA muunnetaan vastaavaksi DFA:ksi. NFA:ssa, kun tietty syöttö annetaan nykyiselle tilalle, kone siirtyy useisiin tiloihin. Sillä voi olla nolla, yksi tai useampi kuin yksi liike tietyllä syöttösymbolilla. Toisaalta DFA:ssa, kun tietty syöte annetaan nykyiselle tilalle, kone siirtyy vain yhteen tilaan. DFA:lla on vain yksi liike tietyssä syöttösymbolissa.
Olkoon, M = (Q, ∑, δ, q0, F) on NFA, joka hyväksyy kielen L(M). Pitäisi olla vastaava DFA, jota merkitään M' = (Q', ∑', q0', δ', F') siten, että L(M) = L(M').
NFA:n muuntaminen DFA:ksi:
Vaihe 1: Aluksi Q' = ϕ
Vaihe 2: Lisää q0 NFA:ta Q':ään. Etsi sitten siirtymät tästä aloitustilasta.
Vaihe 3: Etsi Q':sta mahdollinen tilajoukko kullekin tulosymbolille. Jos tämä tilajoukko ei ole Q':ssa, lisää se Q':ään.
silmukalle javassa
Vaihe 4: DFA:ssa lopullinen tila ovat kaikki tilat, jotka sisältävät F (NFA:n lopulliset tilat)
Esimerkki 1:
Muunna annettu NFA DFA:ksi.
Ratkaisu: Annetulle siirtymäkaaviolle rakennetaan ensin siirtymätaulukko.
| Osavaltio | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Nyt saadaan δ'-siirtymä tilaan q0.
npm välimuistin tyhjennysvoima
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
Tilan q1 siirtymä δ' saadaan seuraavasti:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
Tilan q2 siirtymä δ' saadaan seuraavasti:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Nyt saadaan δ'-siirtymä [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] Tila [q1, q2] on myös lopullinen tila, koska se sisältää lopputilan q2. Siirtymätaulukko rakennetulle DFA:lle on:
java silmukan loppu
| Osavaltio | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Siirtymäkaavio tulee olemaan:
Tila q2 voidaan eliminoida, koska q2 on saavuttamaton tila.
Esimerkki 2:
Muunna annettu NFA DFA:ksi.
Ratkaisu: Annetulle siirtymäkaaviolle rakennetaan ensin siirtymätaulukko.
pinot java
| Osavaltio | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Nyt saadaan δ'-siirtymä tilaan q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] Tilan q1 siirtymä δ' saadaan seuraavasti:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Nyt saadaan δ'-siirtymä [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] Samalla lailla,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Kuten annetussa NFA:ssa, q1 on lopullinen tila, niin DFA:ssa missä tahansa q1 on olemassa, tilasta tulee lopullinen tila. Näin ollen DFA:ssa lopulliset tilat ovat [q1] ja [q0, q1]. Siksi lopputilojen joukko F = {[q1], [q0, q1]}.
lambda-toiminto java
Siirtymätaulukko rakennetulle DFA:lle on:
| Osavaltio | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Siirtymäkaavio tulee olemaan:
Jopa voimme muuttaa DFA:n tilojen nimiä.
Olettaa
A = [q0] B = [q1] C = [q0, q1]
Näillä uusilla nimillä DFA on seuraava:
