Nemdeterminisztikus automata szimulációja
Ha van egy nemdeterminisztikus automatánk, és meg akarjuk tudni, hogy elfogadja-e az adott szót, átalakíthatjuk determinisztikus automatává, kipróbálhatjuk valahogy, vagy használhatunk egy algoritmust, amely az NVA működését szimulálja.
Az algoritmus elve
Az elvet egy megfelelő példán mutatjuk be. Legyen adott ez az automata:
Ez egy nemdeterminisztikus véges automata, amely valamilyen nyelvet fogad el. Most egyáltalán nem kell érdekelnie minket, hogy melyiket. Megnézzük, hogyan zajlik egy ilyen automata számítása a 11001 bemeneti szóra. A gondolatmenet az, hogy feldolgozunk egy szimbólumot a szóból, és megnézzük, hová juthatunk el az azonos szimbólumhoz tartozó többszörös átmeneteknek köszönhetően. Megjegyezzük az összes ilyen állapotot, és a következő lépésben már úgy tekintünk magunkra, mintha „mindegyik állapotban egyszerre” lennénk, és az érdekel majd minket, hová juthatunk ezekből az állapotokból tovább.
Így megjegyezzük azoknak az állapotoknak a halmazát, amelyekben lehetünk, és a szó még el nem olvasott részét. Az elején tehát a ⟨{q0}, 11001⟩ párunk van. A q0 állapotban (kezdőállapot) kezdünk, a bemeneten pedig a 11001 szó áll. Az automata így néz ki, pirossal és vastagon az az állapot van kiemelve, amelyben éppen vagyunk:
Az első szimbólum 1, a q0 állapotból az 1 szimbólumra csak egyetlen átmenet vezet, így a q1 állapotba jutunk. Megjegyezzük a ⟨{q1}, 1001⟩ párt. Az automata így néz ki:
Folytatjuk. A szó el nem olvasott része 1001, ezért megint az 1-re keresünk átmeneteket. Ebből már kettő van – vissza a q0 állapotba, illetve a q3 állapotba. Most mindkét állapotba egyszerre megyünk. Megjegyezzük tehát a ⟨{q0, q3}, 001⟩ párt.
Mi ennek a logikája? Tudjuk, hogy létezik olyan út, amely a kezdőállapotból a 11 szóval egyaránt elvezet a q3 és a q0 állapotba. Még nem tudjuk, melyik ág lesz hasznos, ezért egyszerűen megjegyezzük mindkettőt. Folytatjuk. A bemeneten a 0 szimbólum áll. Most a q0 és a q3 állapotból induló átmeneteket is figyelembe kell vennünk. A q0 állapotból a q1 és a q2 állapotba vezetnek átmenetek, a q3 állapotból pedig vissza a q1 állapotba. Mindezeket az állapotokat beszámítjuk, így megkapjuk a ⟨{q1, q2}, 01⟩ párt:
Ebben a lépésben azonban még nem végeztünk. Látjuk, hogy a q2 állapotból epszilon-átmenet vezet a q4 állapotba. Tudjuk, hogy az epszilon-átmeneten „bármikor továbbmehetünk”, anélkül hogy újabb karaktert olvasnánk. Más szóval – anélkül, hogy a bemeneti szóból újabb szimbólumot olvasnánk, még átléphetünk a q4 állapotba. A q4 állapotot tehát hozzávesszük azokhoz az állapotokhoz, amelyekben lehetünk: ⟨{q1, q2, q4}, 01⟩. Az automatát így színeznénk ki:
A bemeneten ezután 0 következik. Megnézzük, hová léphetünk abból a három állapotból, amelyben vagyunk. A q1 állapotból sehová, mert hiányzik a 0-hoz tartozó átmenet. A számítás ebben az ágban véget ér. A q4 állapotból szintén nem jutunk sehová. A q2 állapotból vissza a q2 állapotba jutunk. Mivel azonban a q2 állapotból megint epszilon-átmenet vezet a q4 állapotba, a q4 állapotba is eljuthatunk. A {q1, q2, q4} állapothalmazból tehát a 0 szimbólumra a {q2, q4} állapothalmazba jutunk, vagyis megkapjuk a ⟨{q2, q4}, 1⟩ párt:
Végül a bemeneten az 1 szimbólum áll. A q2 állapotból sehová sem jutunk, a számítás ebben az ágban véget ér. A q4 állapotból viszont a q3 és a q5 állapotba jutunk. Megkapjuk a ⟨{q3, q5}, ε⟩ párt:
Az automata most elolvasta az egész szót, és két állapotban „található”: q3, q5. Mivel ezek közül legalább az egyik végállapot, az automata elfogadja a 11001 szót.
Az algoritmus
Először szükségünk van egy függvényre, amely paraméterként egy állapothalmazt kap, és kiszámolja, hogy az epszilon-átmenetek segítségével mely további állapotokba juthatunk el. A bemenet tehát egy ⟨Q, Σ, δ, q0, F⟩ automata és egy States állapothalmaz, a kimenet pedig az a halmaz, amely ezeket az állapotokat tartalmazza, kiegészítve azokkal, amelyekbe epszilon-átmenetekkel el lehet jutni. Ezt a műveletet a States halmaz epszilon-lezárásának nevezzük.
Ezt a függvényt használjuk abban a függvényben, amely a nemdeterminisztikus automata működését szimulálja. A bemenet az automata, a w = w1w2… wn bemeneti szó és azon állapotok halmaza, amelyekben az automata éppen található. A kimenet Igen vagy Nem válasz aszerint, hogy az automata elfogadja-e az adott szót, vagy sem.
Ha ellenőrizni akarjuk, hogy az automata elfogadja-e a w szót, a függvényt így hívjuk meg: ComputeNFA(⟨Q, Σ, δ, q0, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q0, F⟩, {q0})).
Források
Fejezetek: Véges automata, Teljes automata, Nemdeterminisztikus véges automata, Nemdeterminisztikus automata szimulációja, NVA átalakítása DVA-vá
