✖

Felesleges állapotok

A véges automatának lehetnek olyan állapotai, amelyekből nem lehet végállapotba jutni, ezért feleslegesek. Az ilyen állapotokat felesleges állapotoknak nevezzük. Ezeket általában el akarjuk távolítani, mert csak feleslegesen bonyolítják az egész automatát.

Példa felesleges állapotokra

Legyen adott ez a véges automata:

Látjuk, hogy ha a q4 vagy a q5 állapotba jutunk, akkor onnan soha többé nem sikerül eljutnunk a q1 vagy q2 végállapotok valamelyikébe. Az ilyen állapotok ezért feleslegesek, és egyszerűen eltávolíthatjuk őket, így egy új automatát kapunk, amely viszont ekvivalens lenne az előzővel; ugyanazt a nyelvet fogadná el. A felesleges állapotok törlése után az automata így nézne ki:

Ugyanazt a nyelvet fogadná el. Vannak azonban esetek, amikor célszerű megtartani néhány felesleges állapotot – például amikor teljes automatát szerkesztünk.

A felesleges állapot definíciója

Legyen adott egy A = ⟨Q, Σ, δ, q0, F⟩ véges automata. Azt mondjuk, hogy a q ∈ Q állapot felesleges, ha nem létezik olyan w ∈ Σ∗ szó és olyan qf ∈ F állapot, hogy

⟨q,w⟩↦∗⟨qf,ε⟩.

Hogyan távolítsuk el a felesleges állapotokat

Feltesszük, hogy a bemeneten egy A = ⟨Q, Σ, δ, q0, F⟩ automata áll, amelyben már nincsenek elérhetetlen állapotok. Fokozatosan megkeressük azokat az állapotokat, amelyek végállapotokba vezetnek, aztán azokat, amelyek olyan állapotokba vezetnek, amelyek végállapotokba vezetnek, és így tovább körbe-körbe. Így megkapjuk az összes nem felesleges állapot halmazát. Az elején felírjuk, hogy S0 = F. A további Si halmazokat i ∈ ℕ esetén (egytől kezdve) a következő szabály szerint építjük fel:

Si={q∈Q|∃a∈Σ:δ(q,a)∈Si−1}∪Si−1

Az összes nem felesleges állapot végső halmazát így fejezhetjük ki:

⋃i=1∞Si.

A felesleges állapotok halmazát pedig így:

Q∖⋃i=1∞Si.

Más szóval: ha fennáll Si = Si + 1, akkor a Q ∖ Si halmaz a felesleges állapotokat tartalmazza. Az eljárást ezen az automatán szemléltetjük:

Először felírjuk az S0 = {q1, q2} egyenlőséget. Ezután az S1 halmazt úgy építjük fel, hogy az S0 halmazhoz hozzáadjuk mindazokat az állapotokat, amelyek az S0 halmaz valamelyik állapotába vezetnek. Hozzáadjuk tehát a q0 és a q3 állapotot, mert a q0 állapotból átmenet vezet a q1 állapotba, a q3 állapotból pedig a q2 állapotba. Megkapjuk az S1 = {q0, q1, q2, q3} halmazt. Mivel S0 ≠ S1, folytatjuk.

Felépítjük az S2 halmazt. Megkeressük tehát az összes olyan állapotot, amelyből el lehet jutni az S1 halmazba, és még nincs benne az S1 halmazban. Ez az egyetlen q6 állapot, amelyből el lehet jutni a q3 állapotba. Megkapjuk az S2 = {q0, q1, q2, q3, q6} halmazt. Mivel S1 ≠ S2, folytatjuk.

Felépítjük az S3 halmazt. Létezik olyan új állapot, amelyből el lehet jutni az S2 halmaz valamelyik állapotába? Nem létezik, a q4 és q5 állapotból nem lehet eljutni az S2 halmaz egyetlen állapotába sem, a többi állapot pedig már benne van az S2 halmazban. Tehát S3 = {q0, q1, q2, q3, q6}. Mivel S2 = S3, az algoritmus véget ér, és az S2 halmaz a nem felesleges állapotok halmaza. A {q4, q5} halmaz azoknak az állapotoknak a halmaza, amelyek feleslegesek.

Az új, felesleges állapotok nélküli ekvivalens automatát formálisan így szerkesztjük meg. Adott az A = ⟨Q, Σ, δ, q0, F⟩ automata, és megszerkesztjük hozzá az ekvivalens, felesleges állapotok nélküli A′ = ⟨Q′, Σ, δ′, q0, F⟩ automatát.

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a), ha δ(q, a) ∈ Q′, különben a δ′(q, a) nincs definiálva

Források

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