NVA átalakítása DVA-vá

Megmutatjuk, hogyan alakítható át egy nemdeterminisztikus automata determinisztikus automatává, ezzel bebizonyítva, hogy a nemdeterminisztikus és a determinisztikus automaták számítási ereje egyenértékű.

Alapgondolat

Legyen adott egy epszilon-átmenetek nélküli ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ nemdeterminisztikus automata. A ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ determinisztikus automatát úgy építjük fel, hogy

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

A δ_D átmeneti függvényt a következőképpen definiáljuk:

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

Mit jelent ez? A nemdeterminisztikus automata egyszerre több állapotban is lehet, így például előfordulhat, hogy a nemdeterminisztikus automatánk a {q₀, q₁} állapotokban van. A következő szimbólum, például az 1 beolvasásával a {q₀, q₂, q₃} állapothalmazba juthatunk. Ugyanennek az automatának a determinisztikus változatában ez úgy jelenik meg, hogy létrehozunk két állapotot, elnevezzük őket a {q₀, q₁}, illetve a {q₀, q₂, q₃} névvel, és az 1 szimbólumra átmenetet vezetünk köztük. Formálisan így az egyik állapotból a másikba jutunk, de az elnevezésnek köszönhetően tudni fogjuk, hogy a nemdeterminisztikus automatában két, illetve három állapotban lennénk.

Példa

Legyen adott ez a nemdeterminisztikus automata:

A determinisztikus automata megszerkesztéséhez mindenekelőtt az új átmeneti függvényt kell megalkotnunk. Ebben segít egy táblázat, amelybe beírjuk az összes átmenetet. Az elején a táblázat így néz ki:

$$\begin{array}{ccc}\text{állapot}/\text{szimbólum}& 0& 1\\ \left\{q_0\right\}\end{array}$$

A bal oldali oszlopban az algoritmus végén a determinisztikus automata összes állapota szerepelni fog. A kitöltött táblázat azután megadja az átmeneti függvényt. Most beírjuk a táblázatba, hogy mely állapotokba jutunk, ha a {q₀} állapotban vagyunk, és a bemeneten a 0 és az 1 szimbólum áll.

$$\begin{array}{ccc}\text{állapot}/\text{szimbólum}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

A q₀ állapotból a 0 szimbólumra csak a q₁ állapotba vezet átmenet, míg az 1 szimbólumra a q₁ és a q₂ állapotba. Most felvesszük a táblázatba a két új állapotot: a {q₁} és a {q₁, q₂} állapotot. Miért? Valahányszor a táblázatba beírunk egy olyan állapothalmazt, amely még nincs a bal oldali oszlopban, ezt az állapothalmazt oda is felvesszük.

$$\begin{array}{ccc}\text{állapot}/\text{szimbólum}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

és ismét kitöltjük. A {q₁, q₂} állapotnál nem szabad elfelejtenünk mindkét állapotot megvizsgálni, vagyis azt, hogy hová jutunk a q₁ állapotból, egyesítve azzal, hogy hová jutunk a q₂ állapotból.

$$\begin{array}{ccc}\text{állapot}/\text{szimbólum}& 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}$$

Kaptunk néhány új állapotot, amelyeket fel kell vennünk a táblázatba:

$$\begin{array}{ccc}\text{állapot}/\text{szimbólum}& 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}$$

…és megint kitöltjük az átmeneteket:

$$\begin{array}{ccc}\text{állapot}/\text{szimbólum}& 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}$$

A {q₀, q₁, q₃}, {q₁} és {q₁,q₂} állapotok már szerepelnek a táblázatban, ezért csak a {q₀,q₁,q₂,q₃} állapotot vesszük fel.

$$\begin{array}{ccc}\text{állapot}/\text{szimbólum}& 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}$$

Új állapotot már nem vettünk fel, így a táblázat ki van töltve. Most már csak megrajzoljuk a diagramot. A determinisztikus automata állapotai az első oszlopban vannak, a 0 és az 1 szimbólumhoz tartozó átmenetek a következő oszlopokban. Minden olyan állapot, amely tartalmaz valamilyen végállapotot az eredeti automatából, ebben az automatában is végállapot lesz. Vagyis minden, a q₃ állapotot tartalmazó állapot végállapot lesz. Az automata így fog kinézni:

Megmutathatjuk, hogy az automata valóban helyesen működik. Próbáljuk elfogadtatni vele a 11001 szót. A determinisztikus automatában ezen az úton megyünk végig

$$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$$

és az automata elfogadná a szót, mert az utolsó állapot, a {q₀, q₁, q₂, q₃} végállapot. A nemdeterminisztikus automatában a szimuláció során ugyanezekbe az állapotokba jutnánk, vagyis a q₀ állapotban kezdenénk, és az 1 szimbólumra a {q₁, q₂} állapotokba jutnánk. A következő 1 szimbólum a {q₀,q₃} állapotokba vinne, és így tovább a további állapotokra. Végül az összes {q₀, q₁, q₂, q₃} állapotban kötnénk ki, és az automata elfogadná a szót.

Források

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