Automa completo

Nella definizione di base di automa a stati finiti non è necessario che da ogni stato esista una transizione per ogni simbolo. Un automa completo è un automa che ha le transizioni definite da ogni stato per tutti i simboli dell’alfabeto di ingresso.

Come costruire un automa completo

Consideriamo questo automa A = ⟨Q, Σ, δ, q₀, F⟩:

Qui non è disegnata la transizione dallo stato q₀ per la lettera «b». Se si verifica una situazione del genere, diciamo che l’automa non accetta la parola in ingresso. Dal punto di vista della formalizzazione, però, può non essere comodo che la funzione di transizione δ non sia definita per alcuni valori; qui, per esempio, non è definita per δ(q₀, b).

Si risolve facilmente costruendo un automa equivalente con uno stato in più: verso questo stato puntano le transizioni «mancanti», questo stato non è finale e tutti gli ingressi successivi restano a ciclare in questo stato. Chiamiamo questo automa automa completo. L’automa equivalente modificato potrebbe quindi essere fatto così:

Abbiamo aggiunto lo stato q_fail. Dagli altri stati abbiamo tracciato una transizione verso di esso se e solo se prima lì la transizione non esisteva. Questo stato non è finale e cicla su se stesso per tutti gli ingressi successivi. Se nell’automa precedente incontravamo una transizione mancante, qui non c’è alcuna transizione mancante e l’automa finirebbe nello stato q_fail.

Possiamo quindi sempre supporre, senza perdita di generalità, che l’automa abbia le transizioni definite per tutte le combinazioni di stati e caratteri dell’alfabeto.

Definizione

Per un automa completo A = ⟨Q, Σ, δ, q₀, F⟩ vale quindi che

$$\mathrm{\forall }q\in Q\mathrm{\forall }a\in \mathrm{\Sigma }\mathrm{\exists }r\in Q:\delta (q,a)=r.$$

Fonti

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