Nadbytečné stavy
Kapitoly: Nedosažitelné stavy, Nadbytečné stavy, Minimalizace automatu
Konečný automat může mít stavy, ze kterých se není možné dostat do koncového stavu a jsou tak zbytečné. Takovým stavům říkáme nedosažitelné stavy. Tyto stavy typicky chceme odstranit, protože pouze zbytečně zkomplikovávají celý automat.
Příklad nadbytečných stavů
Mějme tento konečný automat:
Vidíme, že ve chvíli, kdy se dostaneme do stavů q4 nebo q5, tak už se nám nikdy nepodaří dostat do jednoho z koncových stavů q1 nebo q2. Takové stavy jsou tak nadbytečné a můžeme je prostě odstranit, čímž bychom získali nový automat, který by byl ale ekvivalentní; přijímal by stejný jazyk. Po smazání nadbytečných stavů by automat vypadal takto:
Přijímal by přitom stejný jazyk. Nicméně jsou okamžiky, kdy je vhodné nějaké nadbytečné stavy mít — například když sestrojujeme totální automat.
Definice nadbytečného stavu
Mějme konečný automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$. Řekneme, že stav q ∈ Q je nadbytečný, pokud neexistuje žádné slovo $w \in \Sigma^+$ a žádný stav qf ∈ F takový, že
$$ \left<q, w\right>\mapsto^\ast\left<q_f,\varepsilon\right>. $$
Jak odstranit nadbytečné stavy
Předpokládáme, že na vstupu máme automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$, který už je bez nedosažitelných stavů. Budeme postupně nalézet stavy, které vedou do koncových stavů a pak stavy, které vedou do stavů, které vedou do koncových stavů a tak pořád dokola. Tím získáme množinu všech stavů, které nejsou nadbytečné. Na začátku položíme S0 = F. Budeme sestrojovat další množiny Si pro i ∈ ℕ podle tohoto předpisu:
$$ S_i = \left\{q,|,\forall q \in Q, a \in \Sigma:\quad \delta(q, a)\in S_{i-1}\right\}\cup S_{i-1} $$
Výslednou množinu všech stavů, které nejsou nadbytečné můžeme vyjádřit takto:
$$ \bigcup_{i=1}^{\infty}S_i. $$
A množinu nadbytečných stavů jako
$$ Q \setminus \bigcup_{i=1}^{\infty}S_i. $$
Jinými slovy: pokud platí Si = Si + 1, pak množina Q∖ Si obsahuje nadbytečné stavy. Postup si budeme ilustrovat na tomto automatu:
Jako první položíme rovnost S0 = {q1, q2}. Dále sestavíme množinu S1 tak, že k množině S0 přidáme všechny stavy, které vedou do jednoho ze stavů v množině S0. Přidáme tak stavy q0 a q3, protože z q0 vede přechod do q1 a z q3 vede přechod do q2. Dostaneme S1 = {q0, q1, q2, q3}. Protože S0 ≠ S1, pokračujeme dále.
Sestavíme množinu S2. Hledáme tak všechny stavy, ze kterých se lze dostat do S1 a přitom ještě v S1 nejsou. Je to jediný stav, q6, ze kterého se lze dostat do stavu q3. Dostaneme S2 = {q0, q1, q2, q3, q6}. Protože S1≠ S2, pokračujeme dále.
Sestavíme množinu S3. Existuje nějaký nový stav, ze kterého se lze dostat do některého ze stavů v S2? Neexistuje, ze stavů q4 a q5 se nelze dostat do žádného ze stavů v S2 a ostatní stavy už v S2 jsou. Platí tak, že S3 = {q0, q1, q2, q3, q6}. Protože S2 = S3, algoritmus končí a množina S2 představuje množinu stavů, které nejsou nadbytečné. Množina {q4, q5} je množina stavů, které nadbytečné jsou.
Formálně nový ekvivalentní automat bez nadbytečných symbolů sestavíme takto. Máme automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$ a sestavíme k němu ekvivalentní automat $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F\right>$ bez nadbytečných symbolů.
- $Q^\prime = Q \setminus \bigcup_{i=1}^\infty S_i$
- $\forall q \in Q^\prime, a\in \Sigma:\quad \delta^\prime(q, a) = \delta(q, a)$