V tejto časti budeme diskutovať o spôsobe prevodu NFA na jeho ekvivalent DFA. V NFA, keď je daný konkrétny vstup pre aktuálny stav, stroj prejde do viacerých stavov. Môže mať nula, jeden alebo viac ako jeden pohyb na danom vstupnom symbole. Na druhej strane, v DFA, keď je daný konkrétny vstup pre aktuálny stav, stroj prejde iba do jedného stavu. DFA má iba jeden pohyb na danom vstupnom symbole.
Nech M = (Q, ∑, δ, q0, F) je NFA, ktorá akceptuje jazyk L(M). Mal by existovať ekvivalent DFA označený ako M' = (Q', ∑', q0', 5', F') tak, že L(M) = L(M').
Kroky na konverziu NFA na DFA:
Krok 1: Spočiatku Q' = ϕ
Krok 2: Pridajte q0 NFA do Q'. Potom nájdite prechody z tohto počiatočného stavu.
Krok 3: V Q' nájdite možnú množinu stavov pre každý vstupný symbol. Ak táto množina stavov nie je v Q', pridajte ju do Q'.
Krok 4: V DFA budú konečným stavom všetky štáty, ktoré obsahujú F (finálne stavy NFA)
Príklad 1:
Skonvertujte daný NFA na DFA.
Riešenie: Pre daný prechodový diagram najskôr zostrojíme prechodovú tabuľku.
porovnateľný reťazec
| Štát | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Teraz získame prechod δ' pre stav q0.
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
Prechod δ' pre stav q1 sa získa takto:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
Prechod δ' pre stav q2 sa získa takto:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Teraz získame prechod δ' 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] Stav [q1, q2] je tiež konečný, pretože obsahuje konečný stav q2. Prechodová tabuľka pre vytvorenú DFA bude:
| Štát | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Diagram prechodu bude:
Stav q2 je možné eliminovať, pretože q2 je nedosiahnuteľný stav.
Príklad 2:
Skonvertujte daný NFA na DFA.
Riešenie: Pre daný prechodový diagram najskôr zostrojíme prechodovú tabuľku.
| Štát | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Teraz získame prechod δ' pre stav q0.
je proteínový tuk
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] Prechod δ' pre stav q1 sa získa takto:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Teraz získame prechod δ' na [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] podobne,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Rovnako ako v danom NFA, q1 je konečný stav, potom v DFA kdekoľvek existuje q1, tento stav sa stáva konečným stavom. V DFA sú teda konečné stavy [q1] a [q0, q1]. Preto množina konečných stavov F = {[q1], [q0, q1]}.
Prechodová tabuľka pre vytvorenú DFA bude:
| Štát | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Diagram prechodu bude:
Dokonca aj my môžeme zmeniť názvy štátov DFA.
Predpokladajme
A = [q0] B = [q1] C = [q0, q1]
S týmito novými názvami bude DFA vyzerať takto:
