Stări inaccesibile

Un automat finit poate avea stări în care nu este posibil să ajungem. Astfel de stări se numesc stări inaccesibile. De obicei vrem să le eliminăm, deoarece nu fac decât să complice inutil automatul.

Exemplu de stări inaccesibile

Fie acest automat:

Vedem că orice am face, în starea q₃ nu ajungem niciodată, deoarece nu intră nicio tranziție în ea. Despre starea q₃ spunem că este inaccesibilă. O întrebare: ar fi starea q₃ accesibilă dacă ar intra în ea o tranziție dintr-o altă stare? Dacă am duce o muchie dintr-una din stările q₀, q₁, q₂, q₅, ar fi accesibilă. Dacă am adăuga un alt nod și am duce o tranziție din el…

…atunci, desigur, ambele stări q₃ și q₄ ar fi inaccesibile.

Definiția stării inaccesibile

Definim mai întâi starea accesibilă. Fie un automat finit A = ⟨Q, Σ, δ, q₀, F⟩. Spunem că o stare q ∈ Q este accesibilă dacă există un cuvânt w ∈ Σ^∗ astfel încât

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

Starea q ∈ Q este inaccesibilă dacă nu este accesibilă.

Cum eliminăm stările inaccesibile

Dacă un automat are deja stări inaccesibile, este indicat să le eliminăm. Construim astfel un automat echivalent A′ = ⟨Q′, Σ, δ′, q₀, F′⟩, care va fi fără stări inaccesibile.

Vom construi iterativ mulțimea stărilor accesibile. Începem cu mulțimea S₀ = {q₀}, deoarece starea inițială este cu siguranță accesibilă. Următoarea mulțime o construim astfel:

$$S_i=\{r|\delta (q,a)=r\text{ pentru un }q\in S_{i-1},a\in \mathrm{\Sigma }\}\cup S_{i-1}$$

Pe românește: mulțimea S₀ este mereu dată, iar mulțimea S₁ o construim luând toate stările din mulțimea S₀ și aflând unde duc tranzițiile lor pentru toate simbolurile din Σ. Reunim aceste stări cu mulțimea inițială de stări S₀. Prin același procedeu aflăm mulțimea S₂ și următoarele. Evident, va fi adevărat că S_{i − 1} ⊆ S_i.

Mulțimea stărilor accesibile o putem obține astfel:

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

Poate părea ciudat că încercăm să reunim o infinitate de mulțimi S_i, dar automatul conține doar un număr finit de stări. Asta înseamnă că, la un moment dat, mulțimile S_j și S_{j + 1} și toate cele următoare vor fi egale, așa că, și după reuniunea unei infinități de mulțimi, putem obține o mulțime finită de stări.

Să ne întoarcem la automatul

și să încercăm să găsim mulțimea stărilor accesibile. Începem cu egalitatea de bază

$$S_0=\left\{q_0\right\}$$

Acum calculăm mulțimea S₁. Trebuie să găsim toate tranzițiile din starea q₀ și să adăugăm stările lor țintă la mulțimea S₀. Deoarece avem q₀ → ^a q₁ și q₀ → ^bq₂, mulțimea S₁ va conține în plus stările q₁ și q₂:

$$S_1=\{q_0,q_1,q_2\}$$

În continuare construim mulțimea S₂. Ne uităm unde putem ajunge din stările q₀, q₁, q₂. Singura stare nouă este q₅, în care putem ajunge din starea q₁:

$$S_2=\{q_0,q_1,q_2,q_5\}$$

În continuare construim mulțimea S₃. Putem ajunge din stările q₀, q₁, q₂, q₅ într-o stare nouă? Nu putem, deci mulțimea S₃ va conține aceleași elemente ca S₂:

$$S_3=\{q_0,q_1,q_2,q_5\}$$

Deoarece S₂ = S₃, avem și S₃ = S₄ = S₅ = … Dacă reunim toate mulțimile S_i, obținem mulțimea S₂, pentru că niciun alt element nu se mai adaugă în vreo altă mulțime.

Mulțimea stărilor accesibile ale automatului este deci {q₀, q₁, q₂, q₅}. Stările inaccesibile le obținem printr-o simplă diferență de mulțimi:

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

Mulțimea stărilor inaccesibile ale automatului nostru este {q₃, q₄}. Eliminăm din automatul A toate stările inaccesibile și toate tranzițiile care conțineau o stare inaccesibilă. Adică automatul echivalent fără stări inaccesibile A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ al automatului A = ⟨Q, Σ, δ, q₀, F⟩ îl definim astfel:

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

Surse

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