Overflødige tilstande

En endelig automat kan have tilstande, hvorfra det ikke er muligt at nå en accepttilstand, og som derfor er unødvendige. Sådanne tilstande kalder vi overflødige tilstande. Normalt vil vi gerne fjerne dem, fordi de blot gør hele automaten mere indviklet.

Eksempel på overflødige tilstande

Vi ser på denne endelige automat:

Vi ser, at så snart vi når til tilstandene q₄ eller q₅, lykkes det os aldrig mere at nå en af accepttilstandene q₁ eller q₂. Sådanne tilstande er derfor overflødige, og vi kan simpelthen fjerne dem, hvorved vi får en ny automat, som dog er ækvivalent; den ville acceptere det samme sprog. Efter at have slettet de overflødige tilstande ville automaten se sådan ud:

Den ville altså acceptere det samme sprog. Der er dog tidspunkter, hvor det er hensigtsmæssigt at have nogle overflødige tilstande — for eksempel når vi konstruerer en total automat.

Definition af en overflødig tilstand

Vi har en endelig automat A = ⟨Q, Σ, δ, q₀, F⟩. Vi siger, at en tilstand q ∈ Q er overflødig, hvis der ikke findes noget ord w ∈ Σ^∗ og ingen tilstand q_f ∈ F sådan, at

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

Sådan fjerner du overflødige tilstande

Vi antager, at vi som input har en automat A = ⟨Q, Σ, δ, q₀, F⟩, som allerede er uden uopnåelige tilstande. Vi finder efterhånden de tilstande, der fører til accepttilstande, derefter de tilstande, der fører til tilstande, som fører til accepttilstande, og så fremdeles. Dermed får vi mængden af alle tilstande, der ikke er overflødige. Til at begynde med sætter vi S₀ = F. Vi konstruerer yderligere mængder S_i for i ∈ ℕ efter denne forskrift:

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

Den resulterende mængde af alle tilstande, der ikke er overflødige, kan vi udtrykke sådan:

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

Og mængden af overflødige tilstande som

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

Med andre ord: hvis S_i = S_{i + 1}, så indeholder mængden Q ∖ S_i de overflødige tilstande. Vi illustrerer fremgangsmåden på denne automat:

Først sætter vi S₀ = {q₁, q₂}. Derefter opstiller vi mængden S₁ ved at lægge alle de tilstande til mængden S₀, der fører til en af tilstandene i S₀. Vi tilføjer således tilstandene q₀ og q₃, fordi der fra q₀ går en overgang til q₁, og fra q₃ går en overgang til q₂. Vi får S₁ = {q₀, q₁, q₂, q₃}. Da S₀ ≠ S₁, fortsætter vi.

Vi opstiller mængden S₂. Vi leder altså efter alle tilstande, hvorfra man kan nå S₁, og som endnu ikke er i S₁. Det er den eneste tilstand q₆, hvorfra man kan nå tilstanden q₃. Vi får S₂ = {q₀, q₁, q₂, q₃, q₆}. Da S₁ ≠ S₂, fortsætter vi.

Vi opstiller mængden S₃. Findes der en ny tilstand, hvorfra man kan nå en af tilstandene i S₂? Det gør der ikke, fra tilstandene q₄ og q₅ kan man ikke nå nogen af tilstandene i S₂, og de øvrige tilstande er allerede i S₂. Der gælder altså S₃ = {q₀, q₁, q₂, q₃, q₆}. Da S₂ = S₃, slutter algoritmen, og mængden S₂ er mængden af tilstande, der ikke er overflødige. Mængden {q₄, q₅} er mængden af tilstande, der er overflødige.

Formelt konstruerer vi en ny ækvivalent automat uden overflødige tilstande sådan her. Vi har en automat A = ⟨Q, Σ, δ, q₀, F⟩ og konstruerer til den en ækvivalent automat A′ = ⟨Q′, Σ, δ′, q₀, F⟩ uden overflødige tilstande.

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

Kilder

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