Stati inutili

Un automa a stati finiti può avere stati da cui è impossibile arrivare in uno stato finale e che quindi non servono a nulla. Tali stati si chiamano stati inutili. Di solito vogliamo eliminarli, perché complicano inutilmente l’intero automa.

Esempio di stati inutili

Prendiamo questo automa a stati finiti:

Vediamo che, una volta arrivati negli stati q₄ o q₅, non riusciremo mai più ad arrivare in uno degli stati finali q₁ o q₂. Tali stati sono quindi inutili e possiamo semplicemente eliminarli, ottenendo un nuovo automa che però sarebbe equivalente: accetterebbe lo stesso linguaggio. Dopo aver cancellato gli stati inutili l’automa si presenterebbe così:

Accetterebbe lo stesso linguaggio. Ci sono però casi in cui conviene avere degli stati inutili, ad esempio quando costruiamo un automa completo.

Definizione di stato inutile

Sia A = ⟨Q, Σ, δ, q₀, F⟩ un automa a stati finiti. Diciamo che uno stato q ∈ Q è inutile se non esiste nessuna parola w ∈ Σ^∗ e nessuno stato q_f ∈ F tali che

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

Come eliminare gli stati inutili

Supponiamo di avere in ingresso un automa A = ⟨Q, Σ, δ, q₀, F⟩ già privo di stati irraggiungibili. Troveremo via via gli stati che portano negli stati finali, poi gli stati che portano a stati che portano negli stati finali, e così di seguito. In questo modo otteniamo l’insieme di tutti gli stati che non sono inutili. All’inizio poniamo S₀ = F. Costruiremo gli altri insiemi S_i per i ∈ ℕ^* secondo questa regola:

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

L’insieme risultante di tutti gli stati che non sono inutili si può esprimere così:

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

E l’insieme degli stati inutili così:

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

In altre parole: se vale S_i = S_{i + 1}, allora l’insieme Q ∖ S_i contiene gli stati inutili. Illustriamo il procedimento su questo automa:

Per prima cosa poniamo S₀ = {q₁, q₂}. Poi costruiamo l’insieme S₁ aggiungendo all’insieme S₀ tutti gli stati che portano in uno degli stati dell’insieme S₀. Aggiungiamo quindi gli stati q₀ e q₃, perché da q₀ c’è una transizione verso q₁ e da q₃ una transizione verso q₂. Otteniamo S₁ = {q₀, q₁, q₂, q₃}. Poiché S₀ ≠ S₁, andiamo avanti.

Costruiamo l’insieme S₂. Cerchiamo quindi tutti gli stati da cui si può arrivare in S₁ e che non sono ancora in S₁. È uno solo, q₆, da cui si può arrivare nello stato q₃. Otteniamo S₂ = {q₀, q₁, q₂, q₃, q₆}. Poiché S₁ ≠ S₂, andiamo avanti.

Costruiamo l’insieme S₃. Esiste qualche stato nuovo da cui si può arrivare in uno degli stati di S₂? No: dagli stati q₄ e q₅ non si può arrivare in nessuno degli stati di S₂ e gli altri stati sono già in S₂. Vale quindi S₃ = {q₀, q₁, q₂, q₃, q₆}. Poiché S₂ = S₃, l’algoritmo termina e l’insieme S₂ rappresenta l’insieme degli stati che non sono inutili. L’insieme {q₄, q₅} è l’insieme degli stati inutili.

Formalmente, il nuovo automa equivalente senza stati inutili si costruisce così. Abbiamo l’automa A = ⟨Q, Σ, δ, q₀, F⟩ e costruiamo per esso l’automa equivalente A′ = ⟨Q′, Σ, δ′, q₀, F⟩ privo di stati inutili.

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

Fonti

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