Automaták minimalizálása

Az automata minimalizálásán azt értjük, hogy megkeressük azt az ekvivalens automatát, amelynek a lehető legkevesebb állapota van. Még az az automata is egyszerűsíthető tovább, amelyben nincs felesleges állapot.

Példa

Vegyük ezt az automatát:

Az automata csak a 01 és a 11 szót fogadja el. Ugyanakkor nyilvánvaló, hogy létezik egyszerűbb, három állapotú automata, amely ugyanezt a nyelvet fogadja el. A q₁ és a q₂ állapot összevonható egyetlen új, {q₁, q₂} állapottá, a q₁ vagy q₂ állapotba vezető átmenetek az új állapotba fognak vezetni, és ugyanez igaz a q₁ és q₂ állapotból induló átmenetekre. Ezt az automatát kapjuk:

Ez az automata nyilvánvalóan ugyanazt a nyelvet fogadja el, mint az előző, ugyanakkor kevesebb állapota van.

Az állapotok ekvivalenciája

Legyen adott egy A = ⟨Q, Σ, δ, q₀, F⟩ automata. A q ∈ Q állapot nyelvét, amelyet L(q)-val jelölünk, így definiáljuk:

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Vagyis az A automata kezdőállapotát a q₀ állapotról a q állapotra változtatjuk, és kiszámoljuk az így kapott automata által elfogadott nyelvet. Más szóval az L(q) nyelvben azok a w szavak vannak, amelyekre az A automatában a q állapotból a w szóval az automata valamelyik végállapotába jutunk. Ha visszatérünk az előző automatához, akkor L(q₁) = {1}.

Azt mondjuk, hogy két különböző állapot, a q₁ és a q₂ ekvivalens, ha fennáll

$L (q_{1}) = L (q_{2})$

Mit jelent ez? Ha a q₁, q₂ állapotok ekvivalensek, akkor ha bármelyiküket tesszük meg kezdőállapotnak, ugyanazt a nyelvet fogják generálni. Más szóval: ha az automata a ⟨q₁, w⟩ és a ⟨q₂, w⟩ konfigurációba kerül, akkor mindkét esetben el kell fogadnia, vagy mindkét esetben el kell utasítania a szót.

Ha visszatérünk az előző automatához: a q₁ és a q₂ állapot ekvivalens, mert ha a q₁ állapotban vagyunk, akkor a bemeneti szót már csak akkor fogadhatjuk el, ha a szó el nem olvasott része 1. Ugyanez igaz, ha a q₂ állapotban vagyunk.

Az automata minimalizálásakor tehát az a lényeg, hogy megkeressük az ekvivalens állapotokat, és ezeket az állapotokat úgy távolítsuk el, hogy egyetlen új állapottá vonjuk össze őket, ugyanúgy, ahogy a fenti példában tettük.

Hogyan találjuk meg az ekvivalens állapotokat

Mely állapotok biztosan nem lesznek ekvivalensek? Ha egy végállapotot és egy nem végállapotot veszünk, azok biztosan nem ekvivalensek, mert a végállapot nyelve különbözik a nem végállapot nyelvétől – a végállapot biztosan elfogadja az ε szót, a nem végállapot nem. Az eljárást rögtön egy példán mutatjuk be. Legyen tehát adott ez az automata:

Azzal kezdjük, hogy létrehozunk két állapothalmazt

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Most elkészítjük az átmenetek táblázatát, és megőrizzük az S₁ és S₂ csoportokra vonatkozó információt:

$\begin{array}{ccccc} csoport & állapot & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Most úgy módosítjuk a táblázatot, hogy ne közvetlenül azt írjuk bele, hogy az adott szimbólumra mely állapotokba jutunk, hanem csak azt a csoportot jegyezzük fel, amelybe átmegyünk. Például a q₃ állapotból a 0 szimbólumra a q₅ állapotba jutunk, amely az S₂ csoportban van. A q₅ helyett tehát a táblázatba S₂-t írunk:

$\begin{array}{ccccc} csoport & állapot & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Most tovább osztjuk mindkét csoportot. Mindig azokat az állapotokat tesszük egy csoportba, amelyek minden szimbólumra ugyanazokba a csoportokba mennek át. Például a q₃ és a q₆ állapot nem lesz ugyanabban a csoportban, mert sem a 0, sem az 1 szimbólumra nem ugyanabba a csoportba mennek. Ezzel szemben a q₁ és a q₂ állapot ugyanabban a csoportban lesz, mert egyiküknek sincs átmenete a 0 szimbólumra, és mindketten az 1 szimbólumra az S₁ csoportba mennek. Új csoportokat hozunk létre:

$\begin{array}{ccccc} csoport & állapot & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Minden csoportban ugyanazok az átmenetek vannak. Az újonnan keletkezett csoportokat megjelöljük, és ismét megállapítjuk, hogy az állapotokból ezek közül az új csoportok közül melyikbe vezetnek az átmenetek:

$\begin{array}{ccccc} csoport & állapot & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

Most a csoportok újabb felosztása következne. Látjuk azonban, hogy további osztást már nem végezhetünk, ugyanezeket a csoportokat kapnánk – mert a q₁ és a q₂ állapot átmenetei ugyan a csoportokon belül megegyeznek, de már ugyanabban a csoportban vannak, és az S₄ csoportban nincs más állapot. Az ekvivalens állapotok keresésének algoritmusa véget ért. Minden csoportból elég egy állapotot kiválasztanunk, a többit töröljük, és az összes átmenet, amely a törölt állapotokba vezetett, abba az egy állapotba fog vezetni, amelyet kiválasztottunk.

Választhatjuk például, hogy az új automatánk állapotai a q₃, q₆, q₀, q₁, q₄ legyenek, a q₂ és q₅ állapotot pedig töröljük. Minden átmenet, amely a q₂ állapotba vezetett, most a q₁ állapotba fog vezetni, és minden átmenet, amely a q₅ állapotba vezetett, a q₄ állapotba:

Az automata minimalizálásának menete

Eltávolítjuk az elérhetetlen állapotokat,
eltávolítjuk a felesleges állapotokat,
eltávolítjuk az ekvivalens állapotokat.

Források

Fejezetek: Elérhetetlen állapotok, Felesleges állapotok, Automaták minimalizálása

« Előző: Felesleges állapotok

Következő: Reguláris nyelvek »