Nadbytečné stavy

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 nadbytečné 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ů q₄ nebo q₅, tak už se nám nikdy nepodaří dostat do jednoho z koncových stavů q₁ nebo q₂. 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 = ⟨Q, Σ, δ, q₀, F⟩. Řekneme, že stav q ∈ Q je nadbytečný, pokud neexistuje žádné slovo w ∈ Σ^∗ a žádný stav q_f ∈ F takový, že

$$⟨q,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩.$$

Jak odstranit nadbytečné stavy

Předpokládáme, že na vstupu máme automat A = ⟨Q, Σ, δ, q₀, F⟩, 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 S₀ = F. Budeme sestrojovat další množiny S_i pro i ∈ ℕ podle tohoto předpisu:

$$S_i=\{q\in Q|\mathrm{\exists }a\in \mathrm{\Sigma }:\delta (q,a)\in S_{i-1}\}\cup S_{i-1}$$

Výslednou množinu všech stavů, které nejsou nadbytečné, můžeme vyjádřit takto:

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

A množinu nadbytečných stavů jako

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

Jinými slovy: pokud platí S_i = S_{i + 1}, pak množina Q ∖ S_i obsahuje nadbytečné stavy. Postup si budeme ilustrovat na tomto automatu:

Jako první položíme rovnost S₀ = {q₁, q₂}. Dále sestavíme množinu S₁ tak, že k množině S₀ přidáme všechny stavy, které vedou do jednoho ze stavů v množině S₀. Přidáme tak stavy q₀ a q₃, protože z q₀ vede přechod do q₁ a z q₃ vede přechod do q₂. Dostaneme S₁ = {q₀, q₁, q₂, q₃}. Protože S₀ ≠ S₁, pokračujeme dále.

Sestavíme množinu S₂. Hledáme tak všechny stavy, ze kterých se lze dostat do S₁ a přitom ještě v S₁ nejsou. Je to jediný stav, q₆, ze kterého se lze dostat do stavu q₃. Dostaneme S₂ = {q₀, q₁, q₂, q₃, q₆}. Protože S₁ ≠ S₂, pokračujeme dále.

Sestavíme množinu S₃. Existuje nějaký nový stav, ze kterého se lze dostat do některého ze stavů v S₂? Neexistuje, ze stavů q₄ a q₅ se nelze dostat do žádného ze stavů v S₂ a ostatní stavy už v S₂ jsou. Platí tak, že S₃ = {q₀, q₁, q₂, q₃, q₆}. Protože S₂ = S₃, algoritmus končí a množina S₂ představuje množinu stavů, které nejsou nadbytečné. Množina {q₄, q₅} je množina stavů, které nadbytečné jsou.

Formálně nový ekvivalentní automat bez nadbytečných stavů sestavíme takto. Máme automat A = ⟨Q, Σ, δ, q₀, F⟩ a sestavíme k němu ekvivalentní automat A′ = ⟨Q′, Σ, δ′, q₀, F⟩ bez nadbytečných stavů.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a), pokud δ(q, a) ∈ Q′, jinak δ′(q, a) není definována

Zdroje

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools