Conversione da NFA a DFA

Vediamo come convertire un automa non deterministico in un automa deterministico, dimostrando così che la potenza di calcolo degli automi non deterministici e di quelli deterministici è equivalente.

L’idea di base

Prendiamo un automa non deterministico ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ senza ε-transizioni. Costruiamo un automa deterministico ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ in questo modo:

• Q_D ⊆ 2^Q_N
• Σ_D = Σ_N
• p₀ = {q₀}
• F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

La funzione di transizione δ_D la definiamo così:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\Sigma }}_D:{\delta }_D(Q,a)=\bigcup _{q\in Q}{\delta }_N(q,a)$$

Che cosa significa? Un automa non deterministico può trovarsi contemporaneamente in più stati, quindi può capitare, ad esempio, che il nostro automa non deterministico si trovi negli stati {q₀, q₁}. Leggendo il simbolo successivo, ad esempio 1, possiamo arrivare all’insieme di stati {q₀, q₂, q₃}. Nella versione deterministica dello stesso automa questo si traduce così: creiamo due stati, li chiamiamo {q₀, q₁} e {q₀, q₂, q₃} e introduciamo tra di loro una transizione per il simbolo 1. Formalmente si passa da uno stato all’altro, ma grazie al nome sappiamo che nell’automa non deterministico ci saremmo trovati rispettivamente in due e in tre stati.

Esempio

Prendiamo questo automa non deterministico:

Per costruire l’automa deterministico ci serve soprattutto una nuova funzione di transizione. Ci aiuta una tabella in cui scriviamo tutte le transizioni. All’inizio la tabella si presenta così:

$$\begin{array}{ccc}\text{stato}/\text{simbolo}& 0& 1\\ \left\{q_0\right\}\end{array}$$

Nella colonna di sinistra avremo alla fine dell’algoritmo tutti gli stati dell’automa deterministico. La tabella compilata ci darà poi la funzione di transizione. Ora scriviamo nella tabella in quali stati arriviamo se siamo negli stati {q₀} e in ingresso ci sono i simboli 0 e 1.

$$\begin{array}{ccc}\text{stato}/\text{simbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Dallo stato q₀ per il simbolo 0 c’è una transizione solo verso lo stato q₁, mentre per il simbolo 1 si va negli stati q₁ e q₂. Ora aggiungiamo alla tabella due nuovi stati: {q₁} e {q₁, q₂}. Perché? Ogni volta che nella tabella inseriamo un insieme di stati che non abbiamo ancora nella colonna di sinistra, aggiungiamo lì quell’insieme di stati.

$$\begin{array}{ccc}\text{stato}/\text{simbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

e compiliamo di nuovo. Per lo stato {q₁, q₂} non dimentichiamo di controllare entrambi gli stati, cioè dove arriviamo da q₁ unito a dove arriviamo da q₂.

$$\begin{array}{ccc}\text{stato}/\text{simbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

Abbiamo ottenuto alcuni nuovi stati, che dobbiamo aggiungere alla tabella:

$$\begin{array}{ccc}\text{stato}/\text{simbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}\\ \{q_0,q_3\}\end{array}$$

…e di nuovo completiamo le transizioni:

$$\begin{array}{ccc}\text{stato}/\text{simbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Gli stati {q₀, q₁, q₃}, {q₁} e {q₁,q₂} li abbiamo già, quindi aggiungiamo solo lo stato {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{stato}/\text{simbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

Non abbiamo aggiunto nessun nuovo stato, quindi la tabella è completa. Ora non resta che costruire il diagramma. Gli stati dell’automa deterministico sono nella prima colonna, le transizioni per i simboli 0 e 1 nelle colonne successive. Ogni stato che contiene uno stato finale dell’automa originale sarà finale anche in questo automa. Cioè ogni stato che contiene q₃ sarà uno stato finale. L’automa si presenterà così:

Possiamo mostrare che l’automa funziona davvero correttamente. Proviamo con la parola 11001. Nell’automa deterministico percorriamo il cammino

$$q_0{\to }^1{q}_1,q_2{\to }^1{q}_0,q_3{\to }^0{q}_1{\to }^0{q}_0,q_1,q_3{\to }^1{q}_0,q_1,q_2,q_3$$

e l’automa accetterebbe la parola, perché l’ultimo stato {q₀, q₁, q₂, q₃} è finale. Nell’automa non deterministico, durante la simulazione, arriveremmo agli stessi stati: partiremmo dallo stato q₀ e per il simbolo 1 arriveremmo negli stati {q₁, q₂}. Il simbolo 1 successivo ci porterebbe negli stati {q₀,q₃} e così via per gli stati seguenti. Alla fine ci ritroveremmo in tutti gli stati {q₀, q₁, q₂, q₃} e l’automa accetterebbe la parola.

Fonti

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