NFA:n muuntaminen DFA:ksi

Näytämme, miten epädeterministinen automaatti muunnetaan deterministiseksi automaatiksi, ja todistamme näin, että epädeterminististen ja determinististen automaattien laskentateho on yhtä suuri.

Perusajatus

Olkoon meillä epädeterministinen automaatti (Q_N, Σ_N, δ_N, q₀, F_N) ilman epsilon-siirtymiä. Rakennamme deterministisen automaatin (Q_D, Σ_D, δ_D, p₀, F_D) näin:

• Q_D ⊆ 2^Q_N
• Σ_D = Σ_N
• p₀ = {q₀}
• F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

Siirtymäfunktion δ_D määrittelemme seuraavasti:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\Sigma }}_D:{\delta }_D(Q,a)=\bigcup _{q\in Q}{\delta }_N(q,a)$$

Mitä tämä tarkoittaa? Epädeterministinen automaatti voi olla samanaikaisesti useassa tilassa, joten voimme esimerkiksi päätyä tilanteeseen, jossa epädeterministinen automaattimme on tiloissa {q₀, q₁}. Lukemalla seuraavan symbolin, esimerkiksi 1, voimme päästä tilojen joukkoon {q₀, q₂, q₃}. Saman automaatin deterministisessä versiossa tämä näkyy niin, että luomme kaksi tilaa, nimeämme ne {q₀, q₁} ja {q₀, q₂, q₃} ja lisäämme niiden välille siirtymän symbolille 1. Muodollisesti siirrymme yhdestä tilasta toiseen, mutta nimeämisen ansiosta tiedämme, että epädeterministisessä automaatissa olisimme kahdessa tai kolmessa tilassa.

Esimerkki

Olkoon meillä tämä epädeterministinen automaatti:

Deterministisen automaatin rakentamiseksi tarvitsemme ennen kaikkea uuden siirtymäfunktion. Siinä auttaa taulukko, johon kirjaamme kaikki siirtymät. Alussa taulukko näyttää tältä:

$$\begin{array}{ccc}\text{tila}/\text{symboli}& 0& 1\\ \left\{q_0\right\}\end{array}$$

Vasempaan sarakkeeseen tulee algoritmin lopussa kaikki deterministisen automaatin tilat. Täytetty taulukko määrää sitten siirtymäfunktion. Nyt kirjaamme taulukkoon, mihin tiloihin pääsemme, kun olemme tilassa {q₀} ja syötteenä ovat symbolit 0 ja 1.

$$\begin{array}{ccc}\text{tila}/\text{symboli}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Tilasta q₀ lähtee symbolille 0 siirtymä vain tilaan q₁, kun taas symbolille 1 se lähtee tiloihin q₁ ja q₂. Nyt lisäämme taulukkoon kaksi uutta tilaa: {q₁} ja {q₁, q₂}. Miksi? Aina kun taulukkoon täydennetään jokin tilojen joukko, jota ei vielä ole vasemmassa sarakkeessa, lisäämme sen joukon sinne.

$$\begin{array}{ccc}\text{tila}/\text{symboli}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

ja täydennämme taas. Tilan {q₁, q₂} kohdalla emme saa unohtaa tarkistaa molempia tiloja, eli sitä, minne pääsemme tilasta q₁, yhdisteenä sen kanssa, minne pääsemme tilasta q₂.

$$\begin{array}{ccc}\text{tila}/\text{symboli}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

Saimme useita uusia tiloja, jotka meidän täytyy lisätä taulukkoon:

$$\begin{array}{ccc}\text{tila}/\text{symboli}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}\\ \{q_0,q_3\}\end{array}$$

…ja täydennämme taas siirtymät:

$$\begin{array}{ccc}\text{tila}/\text{symboli}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Tilat {q₀, q₁, q₃}, {q₁} ja {q₁,q₂} meillä on jo, joten lisäämme vain tilan {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{tila}/\text{symboli}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

Emme lisänneet enää yhtään uutta tilaa, joten taulukko on täytetty. Nyt enää piirrämme kaavion. Deterministisen automaatin tilat ovat ensimmäisessä sarakkeessa, siirtymät symboleille 0 ja 1 seuraavissa. Jokainen tila, joka sisältää jonkin alkuperäisen automaatin lopputilan, on lopputila myös tässä automaatissa. Eli jokainen tilaa q₃ sisältävä tila on lopputila. Automaatti näyttää tältä:

Voimme näyttää, että automaatti toimii todella oikein. Yritetään hyväksyä sana 11001. Deterministisessä automaatissa kuljemme polkua

$$q_0{\to }^1{q}_1,q_2{\to }^1{q}_0,q_3{\to }^0{q}_1{\to }^0{q}_0,q_1,q_3{\to }^1{q}_0,q_1,q_2,q_3$$

ja automaatti hyväksyisi sanan, koska viimeinen tila {q₀, q₁, q₂, q₃} on lopputila. Epädeterministisessä automaatissa päätyisimme simuloinnin aikana samoihin tiloihin, eli aloittaisimme tilasta q₀ ja symbolilla 1 päätyisimme tiloihin {q₁, q₂}. Seuraava symboli 1 vie meidät tiloihin {q₀,q₃} jne. seuraavien tilojen osalta. Lopulta päätyisimme kaikkiin tiloihin {q₀, q₁, q₂, q₃} ja automaatti hyväksyisi sanan.

Lähteet

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools