Nemdeterminisztikus véges automata

Az előző fejezetekben bemutatott véges automata (rövidítve VA vagy DVA) mindig determinisztikus volt, ami abban mutatkozott meg, hogy minden pillanatban egyértelmű volt, mit tesz az automata. Most az általánosabb koncepcióval, a nemdeterminisztikus véges automatákkal (rövidítve NVA) foglalkozunk, amelyekben létezhetnek olyan átmenetek, amelyek ugyanabból az állapotból indulnak, és ugyanarra a szimbólumra vonatkoznak.

Példa

Nézd meg az automata következő diagramját:

Mi a különös rajta? Az, hogy a q₀ csúcsból két él vezet a 0 szimbólumra. Ha tehát megpróbáljuk elfogadtatni a 001 szót, úgy tűnik, az automata nem fogja tudni, hogy a q₀ állapotban maradjon-e, vagy a q₁-be vezető átmenetet kövesse. Egy ilyen automata nemdeterminisztikus lenne.

A determinizmus ebben az értelemben azt jelenti, hogy minden helyzetben egyértelmű, mit tesz az automata, nincs tér a kétértelműségnek. A determinisztikus automatának minden állapotra és minden szimbólumra csak egy átmenete van. A nemdeterminizmus kétértelműséget jelent – egy állapotból ugyanarra a szimbólumra akár három átmenet is vezethet.

És akkor hogyan dönt az automata? A nemdeterminisztikus automata mindig azt az átmenetet választja (néha úgy is mondjuk: „kitalálja”), amely oda vezet, hogy a szót elfogadja; ha ez lehetséges.

Ha az automatába beadjuk a 001 szót, akkor az automatának ezek a lehetőségei vannak a szó kezelésére:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

plusz azok a lehetőségek, amikor nem olvassa végig a szót. Az elsőben végig a q₀ állapotban maradt, amit biztosan megtehet, az átmeneti szabályok megengedik. A második ágban bátran továbbment a következő állapotokba, és végül eljutott a q₂ állapotba, amely végállapot. Ebben az ágban az automata elfogadná a szót. A nemdeterminisztikus automata mindig automatikusan azt az ágat választja, amelyben a szót elfogadja, ha ilyen ág létezik.

Hogyan éri el, hogy automatikusan a „kedvező” ágat választja? Elképzelhetjük úgy, hogy a nemdeterminisztikus automata végigmegy az összes lehetséges ágon, és ha talál olyan ágat, amelyben elfogadja a szót, akkor a szót elfogadja. Hogyan járhatná végig az összes ágat? Egyszerűen úgy, hogy amikor olyan állapotban van, amelyből az aktuális szimbólumra n él vezet, az automata n-szer lemásolja magát, és minden másolat más úton megy. Így fokozatosan végigjárjuk az összes lehetőséget.

Az automata számításának ábrázolása fával

Kissé módosítsuk az előző automatát:

A nemdeterminizmus az első állapotban marad. Az előző automata az összes olyan szót elfogadta, amely 01-re végződik. Ez a módosított automata az összes olyan szót elfogadja, amely tartalmazza a 01 részszót. Elfogadja tehát például a 101 vagy a 0101 szót. A számítás összes ágát könnyen szemléltethetjük fával, például a 01010 szó esetén a fa így nézhet ki:

Az elején a q₀ kezdőállapotban vagyunk. A bemeneten a 01010 szó van, az első el nem olvasott karakter a 0. A q₀ állapotból két átmenet vezet a 0 szimbólumra, a q₀ és a q₁ állapotba. A fában ennek a csúcsnak tehát két gyereke lesz: q₀ és q₁. Ezután az 1 szimbólumot olvassuk. Ott nincs kétértelműség, a q₀ és a q₂ állapotba lépünk. Majd a 0 karaktert olvassuk, a bal oldali ágban megint kétértelműség áll elő, a számítást két további ágra osztjuk. Az egyikben megint a q₀ állapotban maradunk, a másikban a q₁-be megyünk. És így tovább.

Figyeld meg, hogy összesen két ág végződik a q₂ állapotban, vagyis végállapotban. A számításnak két olyan ága van, amelyen az automata elfogadhatja az adott szót. Ez az automata tehát elfogadná a 01010 szót. Megpróbálhatunk hasonló fát készíteni az 1000 szóhoz.

A számítás vagy a q₀ állapotban marad, vagy a q₁ állapotba megy, de onnan már nincs hová továbbmennie, mert a bemeneten már csupa nulla van, és a q₁ állapotnak csak az 1 szimbólumra van átmenete. A számítás egyetlen ága sem végződik végállapotban, ezért az automata az 1000 szót nem fogadja el.

Epszilon-átmenetek

A nemdeterminisztikus automatákban ezenfelül használhatunk epszilon-átmeneteket is. Ezek olyan átmenetek, amelyeket bármilyen szimbólum van is a bemeneten, végrehajthatunk, méghozzá úgy, hogy a szóból egyetlen szimbólumot sem olvasunk el. Hogyan írhatnánk olyan nemdeterminisztikus automatát, amely elfogadja az üres szót, az összes olyan szót, amely csupa egyesből áll, és a (10)ⁿ alakú szavakat, vagyis a 10, 1010, … szavakat?

Az automatát két „részautomatára” osztottuk. A felső gondoskodik arról, hogy felismerje a csupa 1-esből álló szavakat, az alsó a (10)ⁿ alakú szavakról gondoskodik. Próbáljuk elfogadtatni a 111 szót. Az automata az elején a q₀ állapotban van, és a bemeneten a 111 szó áll. Mivel rendelkezésére állnak az epszilon-átmenetek, dönthet úgy, hogy a q₁ vagy a q₂ állapotba megy, aszerint, hogy melyik előnyösebb neki. Látjuk, hogy a q₁ állapotba menni lesz előnyös. Az automata átmegy oda. Közben a bemeneten még mindig a 111 szó van! Csak ebben a pillanatban kezdi olvasni a szó szimbólumait, és a q₁ állapotból újra a q₁-be lépni, amíg el nem olvassa az egész szót, és el nem fogadja.

Ha az 1010 szót próbálnánk elfogadtatni, az automata az elején a q₂ állapotba menne, és csak innen kezdené feldolgozni a szimbólumokat, és a szót megint elfogadná.

Az 1100 szóra az automata bármit csinálhatna, az ilyen szót semmiképp sem tudja elfogadni.

Az epszilon-átmenetek és a nemdeterminizmus sok mindenben megkönnyítik a munkánkat, például annak bizonyítása, hogy reguláris nyelvek uniója megint reguláris nyelv, epszilon-átmenetekkel sokkal egyszerűbben leírható, mint a determinisztikus véges automaták esetében. Ebben a bizonyításban ezek voltak a példaautomatáink

és

majd megszerkesztettünk egy véges determinisztikus automatát, amely mindkét nyelv unióját elfogadta. Epszilon-átmenetekkel az ilyen automatát így állíthatjuk össze:

Egyszerűen hozzáadunk egy új kezdőállapotot, belőle két epszilon-átmenet vezet az eredeti automaták eredeti kezdőállapotaiba, és ennyi az egész. Az automata nemdeterminisztikusan dönt, hogy az egyik vagy a másik „részautomatával” próbálja-e elfogadtatni a szót.

A nemdeterminisztikus automata definíciója

Már megmutattuk, miben különbözik a determinisztikus és a nemdeterminisztikus véges automata, már csak formalizálni kell. A determinisztikus véges automatát ⟨Q, Σ, δ, q₀, F⟩ ötösként definiáltuk, ahol Q az állapotok halmaza, Σ az ábécé, δ az átmeneti függvény, q₀ a kezdőállapot, F pedig a végállapotok halmaza. Az egyetlen, ami a nemdeterminisztikus automaták definíciójában megváltozik, az átmeneti függvény definíciója.

A determinisztikus változatban a δ(q, w) függvényhívás csak egy állapotot adhatott vissza, a nemdeterminisztikus változatban viszont több állapotot is visszaadhat – ha egy szimbólumra több átmenet van definiálva. Mivel az epszilon-átmeneteket is definiálnunk kell, a Σ ∪ {ε} halmazt Σ_ε-nal jelöljük, vagyis Σ_ε = Σ ∪ {ε}. A δ függvényt tehát így definiáljuk:

$δ : Q \times Σ_{ε} \to 2^{Q}$

A 2^Q a hatványhalmazt jelöli, a Q halmaz összes részhalmazának halmazát. A számítás formalizálása nagyon hasonló a véges automatákéhoz. Az automata konfigurációja megint a ⟨q, w⟩ ∈ Q × Σ^∗ pár. A ↦ számítási lépés a konfigurációk halmazán értelmezett olyan reláció, hogy

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

akkor és csak akkor, ha q_j ∈ δ(q_i, w₀). Ebben a mondatban volt a legnagyobb különbség. A determinisztikus automatáknál ezt a feltételt q_j = δ(q_i, w₀) alakban írtuk, mert a δ függvény mindig egy állapotot adott vissza. Az átmeneti függvény nemdeterminisztikus változata állapotok halmazát adja vissza, ezért van ott az ∈ jel. A reláció reflexív és tranzitív lezárását megint ↦ ^∗ jelöli. Azt mondjuk, hogy az automata akkor és csak akkor fogadja el a w szót, ha létezik olyan q_f ∈ F, hogy

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

Források

Fejezetek: Véges automata, Teljes automata, Nemdeterminisztikus véges automata, Nemdeterminisztikus automata szimulációja, NVA átalakítása DVA-vá

« Előző: Teljes automata

Következő: Nemdeterminisztikus automata szimulációja »