Epädeterministisen automaatin simulointi

Jos meillä on epädeterministinen automaatti ja haluamme selvittää, hyväksyykö se annetun sanan, voimme muuntaa automaatin deterministiseksi, voimme jotenkin kokeilla tai voimme käyttää algoritmia, joka simuloi NFA:n toimintaa.

Algoritmin periaate

Näytämme periaatteen havainnollisesti sopivan esimerkin avulla. Olkoon meillä tämä automaatti:

Kyseessä on epädeterministinen äärellinen automaatti, joka hyväksyy jonkin kielen. Meidän ei nyt tarvitse lainkaan tietää, minkä. Näytämme, miltä tällaisen automaatin laskenta voi näyttää syötesanalle 11001. Ajatus on tämä: käsittelemme sanan yhden symbolin ja katsomme, minne kaikkialle voimme päästä, kun samalle symbolille on useita siirtymiä. Muistamme kaikki nämä tilat, ja seuraavassa askeleessa oletamme jo olevamme ”kaikissa näissä tiloissa yhtä aikaa” ja meitä kiinnostaa, minne näistä tiloista pääsemme edelleen.

Muistamme siis joukon tiloja, joissa voimme olla, ja sanan lukemattoman osan. Alussa meillä on pari ({q₀}, 11001). Aloitamme tilasta q₀ (alkutila) ja syötteenä on sana 11001. Automaatti näyttää tältä, punaisella ja lihavoituna on korostettu tila, jossa olemme:

Ensimmäinen symboli on 1, tilasta q₀ on symbolille 1 vain yksi siirtymä, joten päädymme tilaan q₁. Muistamme parin ({q₁}, 1001). Automaatti näyttää tältä:

Jatkamme eteenpäin. Sanan lukematon osa on 1001, joten etsimme taas siirtymiä symbolille 1. Niitä on nyt kaksi — takaisin tilaan q₀ ja lisäksi tilaan q₃. Nyt lähdemme molempiin tiloihin yhtä aikaa. Muistamme siis parin ({q₀, q₃}, 001).

Mikä tässä on logiikka? Tiedämme, että alkutilasta on olemassa polku, jolla sanalla 11 päästään sekä tilaan q₃ että tilaan q₀. Emme vielä tiedä, kumpi haara on meille hyödyllinen, joten muistamme yksinkertaisesti molemmat. Jatkamme eteenpäin. Syötteenä on symboli 0. Nyt meidän täytyy katsoa sekä tilasta q₀ että tilasta q₃ lähteviä siirtymiä. Tilasta q₀ lähtevät siirtymät tiloihin q₁ ja q₂, tilasta q₃ lähtee siirtymä takaisin tilaan q₁. Otamme mukaan kaikki nämä tilat, jolloin saamme parin ({q₁, q₂}, 01):

Tämä askel ei kuitenkaan ole vielä valmis. Näemme, että tilasta q₂ lähtee epsilon-siirtymä tilaan q₄. Tiedämme, että epsilon-siirtymän voi tehdä ”milloin tahansa” lukematta seuraavaa merkkiä. Toisin sanoen — lukematta seuraavaa symbolia syötesanasta voimme vielä siirtyä tilaan q₄. Lisäämme siis tilan q₄ niiden tilojen joukkoon, joissa voimme olla: ({q₁, q₂, q₄}, 01). Väritämme automaatin näin:

Seuraavaksi syötteenä on 0. Katsomme, minne voimme siirtyä niistä kolmesta tilasta, joissa olemme. Tilasta q₁ emme voi siirtyä minnekään, koska symbolille 0 ei ole siirtymää. Laskenta tässä haarassa päättyy. Tilasta q₄ emme myöskään pääse mihinkään. Tilasta q₂ pääsemme takaisin tilaan q₂. Mutta koska tilasta q₂ lähtee jälleen epsilon-siirtymä tilaan q₄, voimme päästä myös tilaan q₄. Tilojen joukosta {q₁, q₂, q₄} pääsemme siis symbolilla 0 tilojen joukkoon {q₂, q₄}, ja saamme parin ({q₂, q₄}, 1):

Lopuksi syötteenä on symboli 1. Tilasta q₂ emme pääse minnekään, laskenta tässä haarassa päättyy. Tilasta q₄ pääsemme kuitenkin tiloihin q₃ ja q₅. Saamme parin ({q₃, q₅}, ε):

Automaatti on nyt lukenut koko sanan ja ”on” kahdessa tilassa: q₃, q₅. Koska ainakin yksi niistä on lopputila, automaatti hyväksyy sanan 11001.

Algoritmi

Ensimmäiseksi tarvitsemme funktion, joka ottaa parametrina tilojen joukon ja laskee, mihin tiloihin pääsemme lisäksi epsilon-siirtymien avulla. Syötteenä on siis automaatti (Q, Σ, δ, q₀, F) ja tilojen joukko States, ja tulosteena on näiden tilojen ylijoukko, johon kuuluvat tilat, joihin pääsee epsilon-siirtymien avulla. Tätä operaatiota kutsumme joukon States epsilon-sulkeumaksi.

$$\begin{array}{r}\\ & \mathbf{Function}EpsilonClosure((Q,\mathrm{\Sigma },\delta ,q_0,F),States)\\ & NextStates\leftarrow \mathrm{\varnothing }\\ & \mathbf{ForEach}q\in States\mathbf{Do}\\ & NextStates\leftarrow NextStates\cup \left\{q\right\}\cup \delta (q,\epsilon )\\ & \mathbf{EndFor}\\ & \\ & \mathbf{If}NextStates\setminus States=\mathrm{\varnothing }\mathbf{Do}\\ & \mathbf{Return}States\\ & \mathbf{Else}\\ & \mathbf{Return}EpsilonClosure((Q,\mathrm{\Sigma },\delta ,q_0,F),NextStates)\\ & \mathbf{EndIf}\\ & \mathbf{EndFunction}\\ & \end{array}$$

Käytämme tätä funktiota funktiossa, joka simuloi epädeterministisen automaatin toimintaa. Syötteenä on automaatti, syötesana w = w₁w₂… w_n ja tilojen joukko, joissa automaatti parhaillaan on. Tulosteena on joko vastaus YES (kyllä) tai NO (ei) sen mukaan, hyväksyykö automaatti annetun sanan vai ei.

$$\begin{array}{r}\\ & \mathbf{Function}ComputeNFA((Q,\mathrm{\Sigma },\delta ,q_0,F),w,States)\\ & \mathbf{If}w=ϵ\mathbf{Do}\\ & \mathbf{If}States\cap F\ne \mathrm{\varnothing }\mathbf{Do}\\ & \mathbf{Return}\text{YES}\\ & \mathbf{Else}\\ & \mathbf{Return}\text{NO}\\ & \mathbf{EndIf}\\ & \mathbf{EndIf}\\ & NextStates\leftarrow \mathrm{\varnothing }\\ & \mathbf{ForEach}q\in States\mathbf{Do}\\ & NextStates\leftarrow NextStates\cup \delta (q,w_1)\\ & \mathbf{EndFor}\\ & NextStates\leftarrow EpsilonClosure((Q,\mathrm{\Sigma },\delta ,q_0,F),NextStates)\\ & \mathbf{Return}ComputeNFA((Q,\mathrm{\Sigma },\delta ,q_0,F),w_2{w}_3\dots w_n,NextStates)\\ & \mathbf{EndFunction}\\ & \end{array}$$

Jos haluamme tarkistaa, hyväksyykö automaatti sanan w, kutsumme funktiota näin: ComputeNFA((Q, Σ, δ, q₀, F), w, EpsilonClosure((Q, Σ, δ, q₀, F), {q₀})).

Lähteet

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