Stări neproductive

Un automat finit poate avea stări din care nu este posibil să ajungem într-o stare finală și care sunt, de aceea, inutile. Astfel de stări se numesc stări neproductive. De obicei vrem să le eliminăm, deoarece nu fac decât să complice inutil automatul.

Exemplu de stări neproductive

Fie acest automat finit:

Vedem că, din momentul în care ajungem în stările q₄ sau q₅, nu vom mai reuși niciodată să ajungem într-una dintre stările finale q₁ sau q₂. Astfel de stări sunt neproductive și le putem pur și simplu elimina, obținând un automat nou, dar echivalent; ar accepta același limbaj. După ștergerea stărilor neproductive, automatul ar arăta astfel:

Și ar accepta în continuare același limbaj. Totuși, există situații în care este potrivit să păstrăm unele stări neproductive – de exemplu, când construim un automat complet.

Definiția stării neproductive

Fie un automat finit A = ⟨Q, Σ, δ, q₀, F⟩. Spunem că o stare q ∈ Q este neproductivă dacă nu există niciun cuvânt w ∈ Σ^∗ și nicio stare q_f ∈ F astfel încât

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

Cum eliminăm stările neproductive

Presupunem că la intrare avem un automat A = ⟨Q, Σ, δ, q₀, F⟩ care este deja fără stări inaccesibile. Vom găsi treptat stările care duc în stările finale, apoi stările care duc în stările care duc în stările finale și tot așa mai departe. Astfel obținem mulțimea tuturor stărilor productive. La început punem S₀ = F. Vom construi următoarele mulțimi S_i pentru i ∈ ℕ după această regulă:

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

Mulțimea rezultată a tuturor stărilor productive o putem exprima astfel:

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

Iar mulțimea stărilor neproductive astfel:

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

Cu alte cuvinte: dacă S_i = S_{i + 1}, atunci mulțimea Q ∖ S_i conține stările neproductive. Vom ilustra procedeul pe acest automat:

Mai întâi punem egalitatea S₀ = {q₁, q₂}. Apoi construim mulțimea S₁ adăugând la mulțimea S₀ toate stările care duc într-una dintre stările mulțimii S₀. Adăugăm astfel stările q₀ și q₃, deoarece din q₀ pleacă o tranziție spre q₁, iar din q₃ pleacă o tranziție spre q₂. Obținem S₁ = {q₀, q₁, q₂, q₃}. Deoarece S₀ ≠ S₁, continuăm.

Construim mulțimea S₂. Căutăm deci toate stările din care se poate ajunge în S₁ și care încă nu sunt în S₁. Este o singură stare, q₆, din care se poate ajunge în starea q₃. Obținem S₂ = {q₀, q₁, q₂, q₃, q₆}. Deoarece S₁ ≠ S₂, continuăm.

Construim mulțimea S₃. Există vreo stare nouă din care se poate ajunge în vreuna dintre stările din S₂? Nu există: din stările q₄ și q₅ nu se poate ajunge în niciuna dintre stările din S₂, iar celelalte stări sunt deja în S₂. Deci S₃ = {q₀, q₁, q₂, q₃, q₆}. Deoarece S₂ = S₃, algoritmul se oprește, iar mulțimea S₂ este mulțimea stărilor productive. Mulțimea {q₄, q₅} este mulțimea stărilor care sunt neproductive.

Formal, construim un automat nou echivalent, fără stări neproductive, astfel. Avem automatul A = ⟨Q, Σ, δ, q₀, F⟩ și construim pentru el un automat echivalent A′ = ⟨Q′, Σ, δ′, q₀, F⟩ fără stări neproductive.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a), dacă δ(q, a) ∈ Q′, altfel δ′(q, a) nu este definită

Surse

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