✖

Uoppnåelige tilstander

En endelig automat kan ha tilstander som det ikke er mulig å komme til. Slike tilstander kaller vi uoppnåelige tilstander. Disse tilstandene vil vi vanligvis fjerne, fordi de bare gjør hele automaten unødvendig komplisert.

Eksempel på uoppnåelige tilstander

La oss ha denne automaten:

Vi ser at uansett hva vi gjør, kommer vi aldri til tilstanden q3, for det går ingen overgang til den. Om tilstanden q3 sier vi derfor at den er uoppnåelig. Et spørsmål — ville tilstanden q3 vært oppnåelig hvis det hadde gått en overgang til den fra en annen tilstand? Hvis vi hadde latt en kant gå fra en av tilstandene q0, q1, q2, q5, ville den vært oppnåelig. Hvis vi la til en ny node og lot en overgang gå fra den…

…ville selvfølgelig både tilstanden q3 og tilstanden q4 vært uoppnåelige.

Definisjon av uoppnåelig tilstand

Først definerer vi en oppnåelig tilstand. La oss ha en endelig automat A = ⟨Q, Σ, δ, q0, F⟩. Vi sier at en tilstand q ∈ Q er oppnåelig hvis det finnes et ord w ∈ Σ∗ slik at

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

En tilstand q ∈ Q er uoppnåelig hvis den ikke er oppnåelig.

Hvordan fjerne uoppnåelige tilstander

Hvis en automat allerede har noen uoppnåelige tilstander, er det lurt å fjerne dem. Vi konstruerer en ekvivalent automat A′ = ⟨Q′, Σ, δ′, q0, F′⟩ som er uten uoppnåelige tilstander.

Vi bygger opp mengden av oppnåelige tilstander iterativt. Vi begynner med mengden S0 = {q0}, siden starttilstanden helt sikkert er oppnåelig. Den neste mengden konstruerer vi slik:

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

Med andre ord er mengden S0 alltid gitt, og mengden S1 konstruerer vi ved å ta alle tilstandene fra mengden S0 og finne ut hvor overgangene for alle symbolene fra Σ går. Disse tilstandene slår vi sammen med den opprinnelige mengden av tilstander S0. På samme måte finner vi mengden S2 og de neste. Det vil åpenbart gjelde at Si − 1 ⊆ Si.

Mengden av oppnåelige tilstander kan vi da få slik:

⋃i=1∞Si

Det kan virke rart at vi prøver å slå sammen uendelig mange mengder Si, men automaten inneholder bare et endelig antall tilstander. Det betyr at mengdene Sj og Sj + 1 og alle de neste fra et visst punkt er like, så selv etter å ha slått sammen uendelig mange mengder kan vi få en endelig mengde av tilstander.

La oss gå tilbake til automaten

og prøve å finne mengden av oppnåelige tilstander. Vi begynner med å sette opp den grunnleggende likheten

S0={q0}

Nå regner vi ut mengden S1. Vi må finne alle overgangene fra tilstanden q0 og legge måltilstandene deres til mengden S0. Siden q0 → a q1 og q0 → bq2 gjelder, vil mengden S1 i tillegg inneholde tilstandene q1 og q2:

S1={q0,q1,q2}

Videre konstruerer vi mengden S2. Vi ser på hvor vi kan komme fra tilstandene q0, q1, q2. Den eneste nye tilstanden er q5, som vi kan komme til fra tilstanden q1:

S2={q0,q1,q2,q5}

Videre konstruerer vi mengden S3. Kan vi fra tilstandene q0, q1, q2, q5 komme til en ny tilstand? Det kan vi ikke, så mengden S3 vil inneholde de samme elementene som S2:

S3={q0,q1,q2,q5}

Siden S2 = S3, er også S3 = S4 = S5 = … Hvis vi slår sammen alle Si, får vi mengden S2, for ingen flere elementer kommer til i noen av de neste mengdene.

Mengden av oppnåelige tilstander i automaten er altså lik {q0, q1, q2, q5}. De uoppnåelige tilstandene får vi med en vanlig mengdedifferanse:

Q∖⋃i=1∞Si

Mengden av uoppnåelige tilstander i automaten vår er {q3, q4}. Fra automaten A fjerner vi alle uoppnåelige tilstander og alle overganger som inneholdt en uoppnåelig tilstand. Det betyr at vi til automaten A = ⟨Q, Σ, δ, q0, F⟩ definerer den ekvivalente automaten uten uoppnåelige tilstander A′ = ⟨Q′, Σ, δ′, q0, F′⟩ slik:

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

Kilder

Kapitler: Uoppnåelige tilstander, Overflødige tilstander, Minimering av automat