✖

Onbereikbare toestanden

Een eindige automaat kan toestanden hebben waar je niet kunt komen. Zulke toestanden noemen we onbereikbare toestanden. Die willen we meestal verwijderen, omdat ze de automaat alleen onnodig ingewikkeld maken.

Voorbeeld van onbereikbare toestanden

Neem deze automaat:

We zien dat we, wat we ook doen, nooit in toestand q3 komen, want er loopt geen enkele overgang naartoe. We zeggen daarom dat toestand q3 onbereikbaar is. Een vraag: zou toestand q3 bereikbaar zijn als er wel een overgang vanuit een andere toestand naartoe liep? Als we een pijl zouden trekken vanuit een van de toestanden q0, q1, q2, q5, zou hij bereikbaar zijn. En als we nog een knoop zouden toevoegen en een overgang daarvandaan zouden trekken…

…dan zouden natuurlijk beide toestanden q3 en q4 onbereikbaar zijn.

Definitie van een onbereikbare toestand

Eerst definiëren we een bereikbare toestand. Neem een eindige automaat A = ⟨Q, Σ, δ, q0, F⟩. We zeggen dat een toestand q ∈ Q bereikbaar is als er een woord w ∈ Σ∗ bestaat zodat

⟨q0,w⟩↦∗⟨q,ε⟩.

Een toestand q ∈ Q is onbereikbaar als hij niet bereikbaar is.

Hoe verwijder je onbereikbare toestanden

Als een automaat al onbereikbare toestanden heeft, is het verstandig ze te verwijderen. We construeren dus een equivalente automaat A′ = ⟨Q′, Σ, δ′, q0, F′⟩ zonder onbereikbare toestanden.

We bouwen iteratief de verzameling bereikbare toestanden op. We beginnen met de verzameling S0 = {q0}, want de begintoestand is zeker bereikbaar. De volgende verzameling bouwen we zo op:

Si={r|δ(q,a)=r voor zekere q∈Si−1,a∈Σ}∪Si−1

In gewone woorden: de verzameling S0 is altijd gegeven, de verzameling S1 bouwen we op door alle toestanden uit de verzameling S0 te nemen en te kijken waar de overgangen voor alle symbolen uit Σ heen lopen. Die toestanden verenigen we met de oorspronkelijke verzameling toestanden S0. Op dezelfde manier vinden we de verzameling S2 en de volgende. Er geldt duidelijk Si − 1 ⊆ Si.

De verzameling bereikbare toestanden krijgen we dan zo:

⋃i=1∞Si

Het kan vreemd lijken dat we oneindig veel verzamelingen Si proberen te verenigen, maar een automaat bevat maar een eindig aantal toestanden. Dat betekent dat op een zeker moment de verzamelingen Sj en Sj + 1 en alle volgende gelijk zijn, zodat we ook na het verenigen van oneindig veel verzamelingen een eindige verzameling toestanden kunnen krijgen.

We gaan terug naar de automaat

en proberen de verzameling bereikbare toestanden te vinden. We beginnen met de basisgelijkheid

S0={q0}

Nu berekenen we de verzameling S1. We moeten dus alle overgangen vanuit toestand q0 vinden en hun doeltoestanden toevoegen aan de verzameling S0. Omdat q0 → a q1 en q0 → bq2 gelden, bevat de verzameling S1 er de toestanden q1 en q2 bij:

S1={q0,q1,q2}

Vervolgens construeren we de verzameling S2. We kijken waar we overal heen kunnen vanuit de toestanden q0, q1, q2. De enige nieuwe toestand is q5, die we vanuit toestand q1 kunnen bereiken:

S2={q0,q1,q2,q5}

Daarna bouwen we de verzameling S3 op. Kunnen we vanuit de toestanden q0, q1, q2, q5 in een nieuwe toestand komen? Nee, dus de verzameling S3 bevat dezelfde elementen als S2:

S3={q0,q1,q2,q5}

Omdat S2 = S3, geldt ook S3 = S4 = S5 = … Als we alle Si verenigen, krijgen we de verzameling S2, want er komt in geen enkele volgende verzameling nog een element bij.

De verzameling bereikbare toestanden van de automaat is dus gelijk aan {q0, q1, q2, q5}. De onbereikbare toestanden krijgen we met een gewoon verschil van verzamelingen:

Q∖⋃i=1∞Si

De verzameling onbereikbare toestanden van onze automaat is {q3, q4}. We verwijderen uit de automaat A alle onbereikbare toestanden en alle overgangen die een onbereikbare toestand bevatten. Dat wil zeggen dat we de equivalente automaat zonder onbereikbare toestanden A′ = ⟨Q′, Σ, δ′, q0, F′⟩ bij de automaat A = ⟨Q, Σ, δ, q0, F⟩ als volgt definiëren:

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
  • F′=F∩Q′=F∩⋃i=1∞Si

Bronnen

Hoofdstukken: Onbereikbare toestanden, Overbodige toestanden, Minimalisatie van een automaat