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)$

Zdroje