✖

Elérhetetlen állapotok

A véges automatának lehetnek olyan állapotai, amelyekbe nem lehet eljutni. Az ilyen állapotokat elérhetetlen állapotoknak nevezzük. Ezeket általában el akarjuk távolítani, mert csak feleslegesen bonyolítják az egész automatát.

Példa elérhetetlen állapotokra

Legyen adott ez az automata:

Látjuk, hogy bármit teszünk, a q3 állapotba soha nem jutunk el, mert nem vezet bele egyetlen átmenet sem. A q3 állapotról ezért azt mondjuk, hogy elérhetetlen. Egy kérdés – elérhető lenne a q3 állapot, ha valamelyik másik állapotból átmenet vezetne bele? Ha a q0, q1, q2, q5 állapotok valamelyikéből élt vezetnénk bele, akkor elérhető lenne. Ha felvennénk egy újabb csúcsot, és abból vezetnénk átmenetet…

…akkor természetesen mind a q3, mind a q4 állapot elérhetetlen lenne.

Az elérhetetlen állapot definíciója

Először az elérhető állapotot definiáljuk. Legyen adott egy A = ⟨Q, Σ, δ, q0, F⟩ véges automata. Azt mondjuk, hogy a q ∈ Q állapot elérhető, ha létezik olyan w ∈ Σ∗ szó, hogy

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

A q ∈ Q állapot elérhetetlen, ha nem elérhető.

Hogyan távolítsuk el az elérhetetlen állapotokat

Ha az automatának már vannak elérhetetlen állapotai, érdemes őket eltávolítani. Megszerkesztjük tehát az ekvivalens A′ = ⟨Q′, Σ, δ′, q0, F′⟩ automatát, amelyben nincsenek elérhetetlen állapotok.

Az elérhető állapotok halmazát iteratívan építjük fel. Az S0 = {q0} halmazzal kezdjük, mert a kezdőállapot biztosan elérhető. A következő halmazt így építjük fel:

Si={r|δ(q,a)=r valamely q∈Si−1,a∈Σ}∪Si−1

Magyarán: az S0 halmaz mindig adott, az S1 halmazt úgy építjük fel, hogy vesszük az S0 halmaz összes állapotát, és megnézzük, hová vezetnek belőlük átmenetek a Σ összes szimbólumára. Ezeket az állapotokat egyesítjük az eredeti S0 állapothalmazzal. Ugyanígy határozzuk meg az S2 és a további halmazokat. Nyilvánvalóan igaz, hogy Si − 1 ⊆ Si.

Az elérhető állapotok halmazát ekkor így kaphatjuk meg:

⋃i=1∞Si

Különösnek tűnhet, hogy végtelen sok Si halmazt akarunk egyesíteni, csakhogy az automatának csak véges számú állapota van. Ez azt jelenti, hogy egy ponton az Sj és az Sj + 1 halmaz, és az összes további is egyenlő lesz, így végtelen sok halmaz egyesítése után is véges állapothalmazt kaphatunk.

Térjünk vissza az automatához

és próbáljuk megkeresni az elérhető állapotok halmazát. Azzal kezdjük, hogy felírjuk az alapegyenlőséget

S0={q0}

Most kiszámítjuk az S1 halmazt. Meg kell keresnünk a q0 állapotból induló összes átmenetet, és a céljukként szereplő állapotokat hozzá kell adnunk az S0 halmazhoz. Mivel fennáll q0 → a q1 és q0 → bq2, az S1 halmaz ezenfelül a q1 és a q2 állapotot is tartalmazni fogja:

S1={q0,q1,q2}

Ezután megszerkesztjük az S2 halmazt. Megnézzük, hová juthatunk el a q0, q1, q2 állapotokból. Az egyetlen új állapot a q5, amelybe a q1 állapotból juthatunk:

S2={q0,q1,q2,q5}

Ezután összeállítjuk az S3 halmazt. Eljuthatunk a q0, q1, q2, q5 állapotokból valamilyen új állapotba? Nem, ezért az S3 halmaz ugyanazokat az elemeket tartalmazza, mint az S2:

S3={q0,q1,q2,q5}

Mivel S2 = S3, ezért S3 = S4 = S5 = … is igaz. Ha az összes Si halmazt egyesítjük, az S2 halmazt kapjuk, mert egyetlen további halmazba sem kerül már újabb elem.

Az automata elérhető állapotainak halmaza tehát {q0, q1, q2, q5}. Az elérhetetlen állapotokat egyszerű halmazkülönbséggel kapjuk meg:

Q∖⋃i=1∞Si

Az automatánk elérhetetlen állapotainak halmaza {q3, q4}. Eltávolítjuk az A automatából az összes elérhetetlen állapotot és az összes olyan átmenetet, amely valamelyik elérhetetlen állapotot tartalmazta. Az A = ⟨Q, Σ, δ, q0, F⟩ automatához tartozó, elérhetetlen állapotok nélküli ekvivalens A′ = ⟨Q′, Σ, δ′, q0, F′⟩ automatát tehát így definiáljuk:

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
  • F′=F∩Q′=F∩⋃i=1∞Si

Források

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