Overbodige toestanden

Een eindige automaat kan toestanden hebben vanwaaruit je niet in een eindtoestand kunt komen en die dus overbodig zijn. Zulke toestanden noemen we overbodige toestanden. Die willen we meestal verwijderen, omdat ze de automaat alleen onnodig ingewikkeld maken.

Voorbeeld van overbodige toestanden

Neem deze eindige automaat:

We zien dat we, zodra we in toestand q₄ of q₅ komen, nooit meer in een van de eindtoestanden q₁ of q₂ kunnen komen. Zulke toestanden zijn dus overbodig en we kunnen ze gewoon verwijderen, waardoor we een nieuwe automaat krijgen die equivalent is; hij zou dezelfde taal accepteren. Na het verwijderen van de overbodige toestanden zou de automaat er zo uitzien:

Hij zou daarbij dezelfde taal accepteren. Toch zijn er momenten waarop het handig is om enkele overbodige toestanden te hebben — bijvoorbeeld als we een totale automaat construeren.

Definitie van een overbodige toestand

Neem een eindige automaat A = ⟨Q, Σ, δ, q₀, F⟩. We zeggen dat een toestand q ∈ Q overbodig is als er geen enkel woord w ∈ Σ^∗ en geen enkele toestand q_f ∈ F bestaat zodat

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

Hoe verwijder je overbodige toestanden

We gaan ervan uit dat de invoer een automaat A = ⟨Q, Σ, δ, q₀, F⟩ is die al geen onbereikbare toestanden meer heeft. We vinden stap voor stap de toestanden die naar eindtoestanden leiden, dan de toestanden die naar toestanden leiden die naar eindtoestanden leiden, en zo steeds verder. Zo krijgen we de verzameling van alle toestanden die niet overbodig zijn. Aan het begin stellen we S₀ = F. We construeren verder verzamelingen S_i voor i ∈ ℕ volgens dit voorschrift:

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

De resulterende verzameling van alle toestanden die niet overbodig zijn, kunnen we zo uitdrukken:

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

En de verzameling overbodige toestanden als

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

Met andere woorden: als S_i = S_{i + 1} geldt, dan bevat de verzameling Q ∖ S_i de overbodige toestanden. We illustreren de werkwijze aan deze automaat:

Eerst stellen we S₀ = {q₁, q₂}. Daarna bouwen we de verzameling S₁ op door aan de verzameling S₀ alle toestanden toe te voegen die naar een van de toestanden in de verzameling S₀ leiden. We voegen dus de toestanden q₀ en q₃ toe, omdat vanuit q₀ een overgang naar q₁ loopt en vanuit q₃ een overgang naar q₂. We krijgen S₁ = {q₀, q₁, q₂, q₃}. Omdat S₀ ≠ S₁, gaan we verder.

We bouwen de verzameling S₂ op. We zoeken dus alle toestanden vanwaaruit je in S₁ kunt komen en die nog niet in S₁ zitten. Dat is één toestand, q₆, vanwaaruit je in toestand q₃ kunt komen. We krijgen S₂ = {q₀, q₁, q₂, q₃, q₆}. Omdat S₁ ≠ S₂, gaan we verder.

We bouwen de verzameling S₃ op. Bestaat er een nieuwe toestand vanwaaruit je in een van de toestanden in S₂ kunt komen? Nee, vanuit de toestanden q₄ en q₅ kun je in geen enkele toestand in S₂ komen en de overige toestanden zitten al in S₂. Er geldt dus S₃ = {q₀, q₁, q₂, q₃, q₆}. Omdat S₂ = S₃, stopt het algoritme en stelt de verzameling S₂ de verzameling toestanden voor die niet overbodig zijn. De verzameling {q₄, q₅} is de verzameling toestanden die wel overbodig zijn.

Formeel construeren we een nieuwe equivalente automaat zonder overbodige toestanden als volgt. We hebben een automaat A = ⟨Q, Σ, δ, q₀, F⟩ en construeren daarbij een equivalente automaat A′ = ⟨Q′, Σ, δ′, q₀, F⟩ zonder overbodige toestanden.

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

Bronnen

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