✖

Uopnåelige tilstande

En endelig automat kan have tilstande, som det ikke er muligt at komme til. Sådanne tilstande kalder vi uopnåelige tilstande. Disse tilstande vil vi typisk gerne fjerne, fordi de blot gør hele automaten unødigt kompliceret.

Eksempel på uopnåelige tilstande

Vi ser på denne automat:

Vi ser, at uanset hvad vi gør, kommer vi aldrig til tilstanden q3, fordi der ikke går nogen overgang til den. Om tilstanden q3 siger vi derfor, at den er uopnåelig. Et spørgsmål — ville tilstanden q3 være opnåelig, hvis der gik en overgang til den fra en anden tilstand? Hvis vi trak en kant fra en af tilstandene q0, q1, q2, q5, ville den være opnåelig. Hvis vi tilføjede en ekstra knude og trak en overgang fra den…

…ville både tilstanden q3 og q4 naturligvis være uopnåelige.

Definition af en uopnåelig tilstand

Først definerer vi en opnåelig tilstand. Vi har en endelig automat A = ⟨Q, Σ, δ, q0, F⟩. Vi siger, at tilstanden q ∈ Q er opnåelig, hvis der findes et ord w ∈ Σ∗, således at

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

Tilstanden q ∈ Q er uopnåelig, hvis den ikke er opnåelig.

Sådan fjerner vi uopnåelige tilstande

Hvis en automat allerede har nogle uopnåelige tilstande, er det hensigtsmæssigt at fjerne dem. Vi konstruerer derfor en ækvivalent automat A′ = ⟨Q′, Σ, δ′, q0, F′⟩, som er uden uopnåelige tilstande.

Vi vil iterativt opbygge mængden af opnåelige tilstande. Vi begynder med mængden S0 = {q0}, fordi starttilstanden helt sikkert er opnåelig. Den næste mængde danner vi sådan:

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

Sagt på dansk er mængden S0 altid givet, mængden S1 danner vi ved at tage alle tilstande fra mængden S0 og finde ud af, hvor alle overgangene for alle symboler fra Σ fører hen. Disse tilstande forener vi med den oprindelige mængde af tilstande S0. På samme måde finder vi mængden S2 og de næste. Det gælder åbenbart, at Si − 1 ⊆ Si.

Mængden af opnåelige tilstande kan vi så få således:

⋃i=1∞Si

Det kan se mærkeligt ud, at vi forsøger at forene uendeligt mange mængder Si, men automaten indeholder kun et endeligt antal tilstande. Det betyder, at mængderne Sj og Sj + 1 og alle de følgende på et tidspunkt er ens, så også efter foreningen af uendeligt mange mængder kan vi få en endelig mængde af tilstande.

Lad os vende tilbage til automaten

og prøve at finde mængden af opnåelige tilstande. Vi begynder med at opstille den grundlæggende ligning

S0={q0}

Nu beregner vi mængden S1. Vi skal altså finde alle overgange fra tilstanden q0 og tilføje deres måltilstande til mængden S0. Da q0 → a q1 og q0 → bq2 gælder, vil mængden S1 desuden indeholde tilstandene q1 og q2:

S1={q0,q1,q2}

Dernæst konstruerer vi mængden S2. Vi ser på, hvor vi overalt kan komme hen fra tilstandene q0, q1, q2. Den eneste nye tilstand er q5, som vi kan komme til fra tilstanden q1:

S2={q0,q1,q2,q5}

Dernæst opstiller vi mængden S3. Kan vi fra tilstandene q0, q1, q2, q5 komme til en ny tilstand? Det kan vi ikke, så mængden S3 kommer til at indeholde de samme elementer som S2:

S3={q0,q1,q2,q5}

Da S2 = S3, er også S3 = S4 = S5 = … Hvis vi forener alle Si, får vi mængden S2, fordi der ikke kommer flere elementer til i nogen af de følgende mængder.

Mængden af opnåelige tilstande i automaten er således lig med {q0, q1, q2, q5}. De uopnåelige tilstande får vi ved en simpel mængdedifferens:

Q∖⋃i=1∞Si

Mængden af uopnåelige tilstande i vores automat er {q3, q4}. Vi fjerner fra automaten A alle uopnåelige tilstande og alle overgange, der indeholdt en uopnåelig tilstand. Dvs. at den ækvivalente automat uden uopnåelige tilstande A′ = ⟨Q′, Σ, δ′, q0, F′⟩ til automaten A = ⟨Q, Σ, δ, q0, F⟩ definerer vi som:

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

Kilder

Kapitler: Uopnåelige tilstande, Overflødige tilstande, Minimering af automat