✖

Stati irraggiungibili

Un automa a stati finiti può avere stati in cui è impossibile arrivare. Tali stati si chiamano stati irraggiungibili. Di solito vogliamo eliminarli, perché complicano inutilmente l’intero automa.

Esempio di stati irraggiungibili

Prendiamo questo automa:

Vediamo che, qualunque cosa facciamo, nello stato q3 non arriveremo mai, perché non vi entra nessuna transizione. Diciamo quindi che lo stato q3 è irraggiungibile. Una domanda: lo stato q3 sarebbe raggiungibile se vi entrasse una transizione da un altro stato? Se vi facessimo entrare un arco da uno degli stati q0, q1, q2, q5, sarebbe raggiungibile. E se aggiungessimo un altro nodo e facessimo partire una transizione da quello…

…allora naturalmente sia lo stato q3 sia lo stato q4 sarebbero irraggiungibili.

Definizione di stato irraggiungibile

Definiamo per prima cosa lo stato raggiungibile. Sia A = ⟨Q, Σ, δ, q0, F⟩ un automa a stati finiti. Diciamo che uno stato q ∈ Q è raggiungibile se esiste una parola w ∈ Σ∗ tale che

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

Uno stato q ∈ Q è irraggiungibile se non è raggiungibile.

Come eliminare gli stati irraggiungibili

Se un automa ha già degli stati irraggiungibili, conviene eliminarli. Costruiamo quindi un automa equivalente A′ = ⟨Q′, Σ, δ′, q0, F′⟩ privo di stati irraggiungibili.

Costruiamo iterativamente l’insieme degli stati raggiungibili. Partiamo dall’insieme S0 = {q0}, perché lo stato iniziale è sicuramente raggiungibile. L’insieme successivo si costruisce così:

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

In parole: l’insieme S0 è sempre dato; l’insieme S1 lo costruiamo prendendo tutti gli stati dell’insieme S0 e scoprendo dove portano le transizioni per tutti i simboli di Σ. Questi stati li uniamo all’insieme di stati originale S0. Con lo stesso procedimento troviamo l’insieme S2 e i successivi. Evidentemente vale Si − 1 ⊆ Si.

L’insieme degli stati raggiungibili si ottiene allora così:

⋃i=1∞Si

Può sembrare strano che cerchiamo di unire infiniti insiemi Si, ma l’automa contiene solo un numero finito di stati. Questo significa che a un certo punto gli insiemi Sj e Sj + 1 e tutti i successivi saranno uguali, quindi anche dopo l’unione di infiniti insiemi possiamo ottenere un insieme finito di stati.

Torniamo all’automa

e proviamo a trovare l’insieme degli stati raggiungibili. Cominciamo ponendo l’uguaglianza di base

S0={q0}

Ora calcoliamo l’insieme S1. Dobbiamo trovare tutte le transizioni dallo stato q0 e aggiungere i loro stati di arrivo all’insieme S0. Poiché valgono q0 → a q1 e q0 → bq2, l’insieme S1 conterrà in più gli stati q1 e q2:

S1={q0,q1,q2}

Poi costruiamo l’insieme S2. Guardiamo dove possiamo arrivare dagli stati q0, q1, q2. L’unico stato nuovo è q5, in cui si arriva dallo stato q1:

S2={q0,q1,q2,q5}

Costruiamo ora l’insieme S3. Dagli stati q0, q1, q2, q5 possiamo arrivare in qualche stato nuovo? No, quindi l’insieme S3 conterrà gli stessi elementi di S2:

S3={q0,q1,q2,q5}

Poiché S2 = S3, anche S3 = S4 = S5 = … Se uniamo tutti gli Si, otteniamo l’insieme S2, perché in nessun insieme successivo si aggiunge più alcun elemento.

L’insieme degli stati raggiungibili dell’automa è quindi {q0, q1, q2, q5}. Gli stati irraggiungibili si ottengono con una semplice differenza di insiemi:

Q∖⋃i=1∞Si

L’insieme degli stati irraggiungibili del nostro automa è {q3, q4}. Dall’automa A eliminiamo tutti gli stati irraggiungibili e tutte le transizioni che contenevano uno stato irraggiungibile. Cioè l’automa equivalente senza stati irraggiungibili A′ = ⟨Q′, Σ, δ′, q0, F′⟩ all’automa A = ⟨Q, Σ, δ, q0, F⟩ si definisce come:

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

Fonti

Capitoli: Stati irraggiungibili, Stati inutili, Minimizzazione di un automa