logo

Konvertavimas iš NFA į DFA

Šiame skyriuje aptarsime NFA konvertavimo į lygiavertį DFA metodą. NFA, kai konkreti įvestis pateikiama dabartinei būsenai, mašina pereina į kelias būsenas. Jame gali būti nulis, vienas arba daugiau nei vienas judesys tam tikru įvesties simboliu. Kita vertus, DFA, kai dabartinei būsenai suteikiama konkreti įvestis, mašina pereina tik į vieną būseną. DFA turi tik vieną judesį su nurodytu įvesties simboliu.

Tegu, M = (Q, ∑, δ, q0, F) yra NFA, kuri priima kalbą L(M). Turėtų būti lygiavertis DFA, pažymėtas M' = (Q', ∑', q0', δ', F'), kad L(M) = L(M').

NFA konvertavimo į DFA žingsniai:

1 žingsnis: Iš pradžių Q' = ϕ

2 žingsnis: Pridėkite q0 NFA prie Q'. Tada suraskite perėjimus iš šios pradžios būsenos.

listnode java

3 veiksmas: Q' raskite galimą kiekvieno įvesties simbolio būsenų rinkinį. Jei šio būsenų rinkinio nėra Q', pridėkite jį prie Q'.

4 veiksmas: DFA galutinė būsena bus visos būsenos, kuriose yra F (galutinės NFA būsenos)

1 pavyzdys:

Konvertuoti nurodytą NFA į DFA.

Konvertavimas iš NFA į DFA

Sprendimas: Pateiktai perėjimo diagramai pirmiausia sudarysime perėjimo lentelę.

valstybė 0 1
→q0 q0 q1
q1 {Q1, Q2} q1
*2 k 2 k {Q1, Q2}

Dabar gausime δ' perėjimą būsenai q0.

 δ'([q0], 0) = [q0] δ'([q0], 1) = [q1] 

Būsenos q1 perėjimas δ' gaunamas taip:

 δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1] 

Būsenos q2 perėjimas δ' gaunamas taip:

 δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2] 

Dabar gausime δ' perėjimą [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] 

Būsena [q1, q2] taip pat yra galutinė būsena, nes joje yra galutinė būsena q2. Sukurtos DFA perėjimo lentelė bus tokia:

valstybė 0 1
→[q0] [q0] [q1]
[q1] [q1, Q2] [q1]
*[q2] [q2] [q1, Q2]
*[Q1, Q2] [q1, Q2] [q1, Q2]

Perėjimo schema bus tokia:

Konvertavimas iš NFA į DFA

Būsena q2 gali būti pašalinta, nes q2 yra nepasiekiama būsena.

2 pavyzdys:

Konvertuoti nurodytą NFA į DFA.

Excel datos skirtumas
Konvertavimas iš NFA į DFA

Sprendimas: Pateiktai perėjimo diagramai pirmiausia sudarysime perėjimo lentelę.

valstybė 0 1
→q0 {Q0, Q1} {1 k.}
* Q1 ϕ {Q0, Q1}

Dabar gausime δ' perėjimą būsenai q0.

 δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] 

Būsenos q1 perėjimas δ' gaunamas taip:

 δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1] 

Dabar gausime δ' perėjimą [q0, q1].

 δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] 

Panašiai,

 δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] 

Kaip ir pateiktoje NFA, q1 yra galutinė būsena, tada DFA, kur egzistuoja q1, ši būsena tampa galutine. Taigi DFA galutinės būsenos yra [q1] ir [q0, q1]. Todėl galutinių būsenų rinkinys F = {[q1], [q0, q1]}.

Sukurtos DFA perėjimo lentelė bus tokia:

Python programos pavyzdžiai
valstybė 0 1
→[q0] [q0, q1] [q1]
*[q1] ϕ [q0, q1]
*[q0, q1] [q0, q1] [q0, q1]

Perėjimo schema bus tokia:

Konvertavimas iš NFA į DFA

Netgi galime pakeisti DFA būsenų pavadinimus.

Tarkime

 A = [q0] B = [q1] C = [q0, q1] 

Su šiais naujais pavadinimais DFA bus tokia:

Konvertavimas iš NFA į DFA