Överflödiga tillstånd

En ändlig automat kan ha tillstånd från vilka det inte går att komma till ett sluttillstånd, och som därför är onödiga. Sådana tillstånd kallar vi överflödiga tillstånd. Vi vill vanligtvis ta bort dem, eftersom de bara gör hela automaten onödigt komplicerad.

Exempel på överflödiga tillstånd

Låt oss ta den här ändliga automaten:

Vi ser att så fort vi hamnar i tillståndet q₄ eller q₅ kommer vi aldrig mer att kunna ta oss till något av sluttillstånden q₁ eller q₂. Sådana tillstånd är överflödiga och vi kan helt enkelt ta bort dem. Då får vi en ny automat som är ekvivalent med den första, dvs. den accepterar samma språk. Efter att de överflödiga tillstånden har tagits bort ser automaten ut så här:

Den accepterar alltså samma språk. Det finns dock tillfällen då det är lämpligt att behålla några överflödiga tillstånd, till exempel när vi konstruerar en total automat.

Definition av ett överflödigt tillstånd

Låt A = ⟨Q, Σ, δ, q₀, F⟩ vara en ändlig automat. Vi säger att ett tillstånd q ∈ Q är överflödigt om det inte finns något ord w ∈ Σ^∗ och något tillstånd q_f ∈ F sådana att

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

Hur du tar bort överflödiga tillstånd

Vi förutsätter att indata är en automat A = ⟨Q, Σ, δ, q₀, F⟩ som redan saknar onåbara tillstånd. Vi hittar stegvis de tillstånd som leder till sluttillstånd, sedan de tillstånd som leder till tillstånd som leder till sluttillstånd, och så vidare. På så sätt får vi mängden av alla tillstånd som inte är överflödiga. I början sätter vi S₀ = F. Vi konstruerar sedan ytterligare mängder S_i för i ∈ ℤ⁺ enligt den här regeln:

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

Den resulterande mängden av alla tillstånd som inte är överflödiga kan vi uttrycka så här:

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

Och mängden av överflödiga tillstånd som

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

Med andra ord: om S_i = S_{i + 1} gäller, innehåller mängden Q ∖ S_i de överflödiga tillstånden. Vi illustrerar förfarandet med den här automaten:

Först sätter vi S₀ = {q₁, q₂}. Sedan bygger vi mängden S₁ genom att till mängden S₀ lägga alla tillstånd som leder till något av tillstånden i S₀. Vi lägger alltså till q₀ och q₃, eftersom det går en övergång från q₀ till q₁ och från q₃ till q₂. Vi får S₁ = {q₀, q₁, q₂, q₃}. Eftersom S₀ ≠ S₁ fortsätter vi.

Vi bygger mängden S₂. Vi söker alla tillstånd från vilka vi kan komma till S₁ och som ännu inte finns i S₁. Det är bara ett tillstånd, q₆, från vilket vi kan komma till q₃. Vi får S₂ = {q₀, q₁, q₂, q₃, q₆}. Eftersom S₁ ≠ S₂ fortsätter vi.

Vi bygger mängden S₃. Finns det något nytt tillstånd från vilket vi kan komma till något av tillstånden i S₂? Nej, från q₄ och q₅ går det inte att komma till något av tillstånden i S₂, och de övriga tillstånden finns redan i S₂. Det gäller alltså att S₃ = {q₀, q₁, q₂, q₃, q₆}. Eftersom S₂ = S₃ tar algoritmen slut, och mängden S₂ är mängden av tillstånd som inte är överflödiga. Mängden {q₄, q₅} är mängden av tillstånd som är överflödiga.

Formellt konstruerar vi en ny ekvivalent automat utan överflödiga tillstånd så här. Vi har automaten A = ⟨Q, Σ, δ, q₀, F⟩ och konstruerar till den en ekvivalent automat A′ = ⟨Q′, Σ, δ′, q₀, F⟩ utan överflödiga tillstånd.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a) om δ(q, a) ∈ Q′, annars är δ′(q, a) inte definierad

Källor

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