Overflødige tilstander

En endelig automat kan ha tilstander som det ikke er mulig å komme til en sluttilstand fra, og som derfor er unødvendige. Slike tilstander kaller vi overflødige tilstander. Disse tilstandene vil vi vanligvis fjerne, fordi de bare gjør hele automaten unødvendig komplisert.

Eksempel på overflødige tilstander

La oss ha denne endelige automaten:

Vi ser at så snart vi kommer til tilstandene q₄ eller q₅, klarer vi aldri mer å komme til en av sluttilstandene q₁ eller q₂. Slike tilstander er overflødige, og vi kan rett og slett fjerne dem. Da får vi en ny automat som er ekvivalent; den aksepterer det samme språket. Etter at de overflødige tilstandene er slettet, ville automaten sett slik ut:

Den ville akseptert det samme språket. Likevel er det tilfeller der det er lurt å ha noen overflødige tilstander — for eksempel når vi konstruerer en total automat.

Definisjon av overflødig tilstand

La oss ha en endelig automat A = ⟨Q, Σ, δ, q₀, F⟩. Vi sier at en tilstand q ∈ Q er overflødig hvis det ikke finnes noe ord w ∈ Σ^∗ og noen tilstand q_f ∈ F slik at

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

Hvordan fjerne overflødige tilstander

Vi antar at vi har automaten A = ⟨Q, Σ, δ, q₀, F⟩ som input, og at den allerede er uten uoppnåelige tilstander. Vi finner etter hvert tilstandene som fører til sluttilstander, så tilstandene som fører til tilstander som fører til sluttilstander, og så videre. Slik får vi mengden av alle tilstander som ikke er overflødige. I begynnelsen setter vi S₀ = F. Vi konstruerer de neste mengdene S_i for i ∈ ℕ etter denne regelen:

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

Den endelige mengden av alle tilstander som ikke er overflødige, kan vi uttrykke slik:

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

Og mengden av overflødige tilstander som

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

Med andre ord: hvis S_i = S_{i + 1} gjelder, inneholder mengden Q ∖ S_i de overflødige tilstandene. Framgangsmåten illustrerer vi på denne automaten:

Først setter vi S₀ = {q₁, q₂}. Videre konstruerer vi mengden S₁ ved å legge til mengden S₀ alle tilstander som fører til en av tilstandene i mengden S₀. Vi legger altså til tilstandene q₀ og q₃, siden det går en overgang fra q₀ til q₁ og en fra q₃ til q₂. Vi får S₁ = {q₀, q₁, q₂, q₃}. Siden S₀ ≠ S₁, fortsetter vi.

Vi konstruerer mengden S₂. Vi leter etter alle tilstander som vi kan komme fra til S₁, og som ikke allerede er i S₁. Det er én eneste tilstand, q₆, som vi kan komme fra til tilstanden q₃. Vi får S₂ = {q₀, q₁, q₂, q₃, q₆}. Siden S₁ ≠ S₂, fortsetter vi.

Vi konstruerer mengden S₃. Finnes det en ny tilstand som vi kan komme fra til noen av tilstandene i S₂? Det gjør det ikke, fra tilstandene q₄ og q₅ kommer vi ikke til noen av tilstandene i S₂, og de andre tilstandene er allerede i S₂. Det gjelder altså at S₃ = {q₀, q₁, q₂, q₃, q₆}. Siden S₂ = S₃, stopper algoritmen, og mengden S₂ er mengden av tilstander som ikke er overflødige. Mengden {q₄, q₅} er mengden av tilstander som er overflødige.

Formelt konstruerer vi en ny ekvivalent automat uten overflødige tilstander slik. Vi har automaten A = ⟨Q, Σ, δ, q₀, F⟩, og til den konstruerer vi den ekvivalente automaten A′ = ⟨Q′, Σ, δ′, q₀, F⟩ uten overflødige tilstander.

• $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 definert

Kilder

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