Nedosažitelné stavy
Kapitoly: Nedosažitelné stavy, Nadbytečné stavy, Minimalizace automatu
Konečný automat může mít stavy, do kterých se není možné dostat. 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 nedosažitelných stavů
Mějme tento automat:
Vidíme, že ať uděláme cokoliv, do stavu q3 se nikdy nedostaneme, protože do něj nevede žádný přechod. O stavu q3 tak řekneme, že je nedosažitelný. Otázka — byl by stav q3 dosažitelný, kdyby do něj nějaký přechod z jiného stavu vedl? Kdybychom vedli hranu z jednoho ze stavů q0, q1, q2, q5, tak by dosažitelný byly. Kdybychom přidali další uzel a vedli přechod z něj…
…tak by samozřejmě oba stavy q3 i q4 byly nedosažitelné.
Definice nedosažitelného stavu
Jako první definujeme dosažitelný stav. Mějme konečný automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$. Řekneme, že stav q ∈ Q je dosažitelný, pokud existuje slovo $w \in \Sigma^\ast$ takové, že
$$ \left<q_0, w\right> \mapsto^\ast \left<q, \varepsilon\right>. $$
Stav q ∈ Q je nedosažitelný, pokud není dosažitelný.
Jak odstranit nedosažitelné stavy
Pokud už automat nějaké nedosažitelné stavy má, je vhodné je odstranit. Sestavíme tak ekvivalentní automat $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F^\prime\right>$, který bude bez nedosažitelných stavů.
Budeme iterativně sestavovat množinu dosažitelných stavů. Začneme s množinou S0 = {q0}, protože počáteční stav je jistě dosažitelný. Další množinu sestavíme takto:
$$ S_i = \left\{r,|, \delta(q, a) = r \mbox{ pro všechna } q \in S_{i-1}, a\in \Sigma \right\} \cup S_{i-1} $$
Česky řečeno, množina S0 je vždy daná, množinu S1 sestavíme tak, že vezmeme všechny stavy z množiny S0 a zjistíme, kam všude vedou přechody pro všechny symboly z $\Sigma$. Tyto stavy sjednotíme s původní množinou stavů S0. Stejným postupem zjistíme množinu S2 a další. Zřejmě bude platit, že $S_{i-1} \subseteq S_{i}$.
Množinu nedosažitelných stavů pak můžeme získat takto:
$$ \bigcup_{i=1}^\infty S_i $$
Může vypadat zvláštně, že se snažíme sjednotit nekonečně mnoho množin Si, jenomže automat obsahuje pouze konečný počet stavů. To znamená, že v jedno chvíli budou množiny Sj a Sj + 1 a všechny další stejné, takže i po sjednocení nekonečně mnoha množin můžeme získat konečnou množinu stavů.
Vraťme se k automatu
a zkusme najít množinu dosažitelných stavů. Začneme tím, že položíme základní rovnost
$$ S_0 = \left\{q_0\right\} $$
Nyní vypočítáme množinu S1. Musíme tak najít všechny přechodu ze stavu q0 a jejich cílové stavy přidat k množině S0. Protože platí $q_0\rightarrow^a q_1$ a $q_0\rightarrow^bq_2$, tak množina S1 bude navíc obsahovat stavy q1 a q2:
$$ S_1 = \left\{q_0, q_1, q_2\right\} $$
Dále zkonstruujeme množinu S2. Podíváme se, kam všude se můžeme dostat ze stavů q0, q1, q2. Jediný nový stav je q5, do kterého se můžme dostat ze stavu q1:
$$ S_2 = \left\{q_0, q_1, q_2, q_5\right\} $$
Dále sestavíme množinu S3. Můžeme se ze stavů q0, q1, q2, q5 dostat do nějakého nového stavu? Nemůžeme, takže množina S3 bude obsahovat stejné prvky jako S2:
$$ S_3 = \left\{q_0, q_1, q_2, q_5\right\} $$
Protože S2 = S3, tak i S3 = S4 = S5 = … Pokud sjednotíme všechny Si, tak získáme množinu S2, protože žádný další prvek už v žádné další množině nepřibude.
Množina dosažitelných stavů automatu je tak rovna {q0, q1, q2, q5}. Nedosažitelné stavy získáme prostým množinovým rozdílem:
$$ Q \setminus \bigcup_{i=1}^\infty S_i $$
Množina nedosažitelných stavů našeho automatu je {q3, q4}. Odstraníme z automatu A všechny nedosažitelné stavy a všechna přechody, které obsahovaly nějaký nedosažitelný stav. Tzn., že ekvivalentní automat bez nedosažitelných stavů $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F^\prime\right>$ k automatu $A=\left<Q, \Sigma, \delta, q_0, F\right>$ definujeme jako:
- $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)$
- $F^\prime = F \cap Q^\prime = F \setminus \bigcup_{i=1}^\infty S_i$