Onåbara tillstånd

En ändlig automat kan ha tillstånd som det inte går att komma till. Sådana tillstånd kallar vi onåbara tillstånd. Vi vill vanligtvis ta bort dem, eftersom de bara gör hela automaten onödigt komplicerad.

Exempel på onåbara tillstånd

Låt oss ta den här automaten:

Vi ser att vi aldrig kan komma till tillståndet q₃, vad vi än gör, eftersom ingen övergång leder dit. Om q₃ säger vi därför att det är onåbart. En fråga: skulle q₃ vara nåbart om någon övergång från ett annat tillstånd ledde dit? Om vi drog en båge från något av tillstånden q₀, q₁, q₂, q₅ skulle det vara nåbart. Om vi lade till ännu en nod och drog en övergång från den…

…så skulle givetvis både q₃ och q₄ vara onåbara.

Definition av ett onåbart tillstånd

Först definierar vi ett nåbart tillstånd. Låt A = ⟨Q, Σ, δ, q₀, F⟩ vara en ändlig automat. Vi säger att ett tillstånd q ∈ Q är nåbart om det finns ett ord w ∈ Σ^∗ sådant att

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

Ett tillstånd q ∈ Q är onåbart om det inte är nåbart.

Hur du tar bort onåbara tillstånd

Om en automat redan har onåbara tillstånd är det lämpligt att ta bort dem. Vi konstruerar då en ekvivalent automat A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ som saknar onåbara tillstånd.

Vi bygger upp mängden av nåbara tillstånd iterativt. Vi börjar med mängden S₀ = {q₀}, eftersom starttillståndet säkert är nåbart. Nästa mängd bygger vi så här:

$$S_i=\{r\mid \delta (q,a)=r\text{ för något }q\in S_{i-1},a\in \mathrm{\Sigma }\}\cup S_{i-1}$$

Med ord: mängden S₀ är alltid given. Mängden S₁ bygger vi genom att ta alla tillstånd i mängden S₀ och ta reda på vart övergångarna för alla symboler i Σ leder. Vi bildar unionen av dessa tillstånd och den ursprungliga mängden S₀. På samma sätt tar vi fram mängden S₂ och de följande. Uppenbarligen gäller S_{i − 1} ⊆ S_i.

Mängden av nåbara tillstånd får vi sedan så här:

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

Det kan verka konstigt att vi försöker göra en union av oändligt många mängder S_i, men automaten innehåller bara ändligt många tillstånd. Det betyder att mängderna S_j och S_{j + 1} och alla följande vid något tillfälle blir likadana, så även efter unionen av oändligt många mängder kan vi få en ändlig mängd av tillstånd.

Vi återvänder till automaten

och försöker hitta mängden av nåbara tillstånd. Vi börjar med att sätta

$$S_0=\left\{q_0\right\}$$

Nu beräknar vi mängden S₁. Vi måste hitta alla övergångar från q₀ och lägga till deras måltillstånd i mängden S₀. Eftersom q₀ → ^a q₁ och q₀ → ^bq₂ gäller kommer mängden S₁ dessutom att innehålla tillstånden q₁ och q₂:

$$S_1=\{q_0,q_1,q_2\}$$

Därefter konstruerar vi mängden S₂. Vi tittar på vart vi kan komma från tillstånden q₀, q₁, q₂. Det enda nya tillståndet är q₅, som vi kan komma till från q₁:

$$S_2=\{q_0,q_1,q_2,q_5\}$$

Sedan bygger vi mängden S₃. Kan vi komma till något nytt tillstånd från q₀, q₁, q₂, q₅? Nej, så mängden S₃ innehåller samma element som S₂:

$$S_3=\{q_0,q_1,q_2,q_5\}$$

Eftersom S₂ = S₃ gäller också S₃ = S₄ = S₅ = … Om vi tar unionen av alla S_i får vi mängden S₂, eftersom inget nytt element tillkommer i någon av de följande mängderna.

Mängden av nåbara tillstånd i automaten är alltså {q₀, q₁, q₂, q₅}. De onåbara tillstånden får vi som en enkel differens av mängder:

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

Mängden av onåbara tillstånd i vår automat är {q₃, q₄}. Vi tar bort alla onåbara tillstånd ur automaten A, och likaså alla övergångar som innehöll något onåbart tillstånd. Den ekvivalenta automaten utan onåbara tillstånd A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ till automaten A = ⟨Q, Σ, δ, q₀, F⟩ definierar vi alltså som:

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
• $F^{\prime }=F\cap Q^{\prime }=F\cap \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$

Källor

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