Automa a stati finiti non deterministico

Un automa a stati finiti non deterministico, o NFA (Non-deterministic Finite Automaton), è un modello di calcolo dove uno stato e un simbolo di input possono condurre a uno o più stati successivi, o addirittura a nessuno stato.

In questo modello le transizioni sono non deterministiche.

Questo significa che ogni stato può avere zero, una o più transizioni per lo stesso simbolo dell'alfabeto, inclusa la transizione ε (epsilon) che non richiede un input.

Per il resto anche l'automa NFA, come gli altri automi, ha uno stato iniziale di partenza e uno o più stati finali di accettazione.

In altre parole, la funzione di transizione mappa ogni coppia di stato e simbolo di input a un insieme di stati. Tuttavia, uno stesso simbolo in uno stato potrebbe generare azioni diverse da parte dell'automa. Quindi il comportamento dell'automa non è prevedibile a priori.

Poiché un singolo simbolo può causare diverse risposte, l'automa NFA deve seguire ogni possibile evoluzione degli stati in parallelo.

Quando un NFA legge un simbolo di input, può seguire molteplici percorsi contemporaneamente creando copie di sé stesso.

L'NFA accetta una stringa se almeno uno dei possibili percorsi termina in uno stato di accettazione.

Il caso delle transizioni ε. Quando si lavora su un automa deterministico bisogna considerare anche le transizioni ε. Se uno stato ha una transizione ε, l'NFA si sposta automaticamente a un nuovo stato senza dover leggere alcun simbolo di input.

Da un punto di vista formale un automa a stati finiti non deterministico è una 5-tupla (Q, Σ, δ, q₀, F), dove:

• Q è un insieme finito di stati,
• Σ è un alfabeto finito,
• δ: Q × Σε → P(Q) è la funzione di transizione,
• q₀ ∈ Q è lo stato iniziale
• F ⊆ Q è l'insieme degli stati di accettazione.

Ognuna di queste componenti contribuisce alle caratteristiche dell'automa NFA. La cosa migliore per capirle è vederle in un esempio pratico.

Esempio pratico

Consideriamo un automa (Q, Σ, δ, q₀, F) non deterministico che riconosce le stringhe contenenti il sottostringa '01'.

• Stati: \( Q = \{ q_0, q_1, q_2 \} \)
• Alfabeto: \( Σ = \{0, 1 \} \)
• Transizioni (δ)
  - Da \( q_0 \) con '0' resta in \( q_0 \)
  - Da \( q_0 \) con '1' può andare a \( q_1 \) o restare in \( q_0 \)
  - Da \( q_1 \) con '1' va a \( q_2 \)
  - Da \( q_1 \) con la stringa vuota 'ε' va a \( q_2 \)
  - Da \( q_2 \) con '0' o con '1' resta in \( q_2 \)
• Stato iniziale: \( q_0 \)
• Stati di accettazione: \( F = \{ q_2 \} \)

Il diagramma degli stati dell'automa è il seguente:

Ecco la tabella delle transizioni dell'automa:

$$ \begin{array}{c|c|c|c}
 & 0 & 1 & \varepsilon \\
\hline
q_0 & \{q_0\} & \{q_0, q_1\} & \emptyset \\
q_1 & \emptyset & \{q_2\} & \{q_2\} \\
q_2 & \{q_2\} & \{q_2\} & \emptyset \\
\end{array} $$

In alcuni stati la funzione di transizione ha diverse azioni per lo stesso simbolo. In altri stati, invece, non ci sono transizioni disponibili per tutti i simboli.

Vediamo cosa accade se l'automa legge la stringa w="010"

• Il primo simbolo della stringa "010" è 0 l'automa resta in q₀.
  
• Il secondo simbolo della stringa "010" è 1 l'automa si trova in q₀ e deve seguire due percorsi: resta in q₀ o si sposta in q₁. Poiché in q₁ c'è anche una stringa vuota ε bisogna considerare anche il caso in cui l'automa si sposta automaticamente in q₂. Quindi, l'automa copia se stesso in tre percorsi e continua a seguirli in parallelo.
  
• Il terzo simbolo della stringa "010" è 0. Vediamo cosa accade in ogni ramo dell'elaborazione. Nel primo ramo l'automa resta in q₀. Nel secondo ramo l'automa si trova in q₁ e non ci sono transizioni disponibili con 0, quindi la stringa viene rifiutata. Nel terzo ramo l'automa si trova in q₂ e resta in q₂.
  
• Nel terzo ramo l'automa NFA si trova in q2 che è uno stato di accettazione, quindi la stringa "010" viene accettata dall'automa.
  

In un automa NFA per accettare una stringa è sufficiente che sia accettata in almeno un ramo della computazione.

La differenza tra DFA e NFA

Le principali differenze tra un automa a stati finiti deterministico (DFA) e non deterministico (NFA) sono le seguenti:

• Automa DFA
  In un DFA (Deterministic Finite Automaton), ogni stato ha esattamente una transizione per ogni simbolo dell'alfabeto. Quindi, la funzione di transizione è una funzione singola.  Generalmente un automa DFA è più semplice da implementare ma potrebbe richiedere più stati.
• Automa NFA
  In un NFA, uno stato può avere molte transizioni per lo stesso simbolo o nessuna, e possono esserci transizioni ε. In questo caso la funzione di transizione non è una funzione matematica ma è più appropriatamente una relazione che mappa uno stato e un simbolo a un insieme di stati. Un automa NFA è più compatto in termini di stati, ma necessita di una gestione più complessa delle transizioni perché deve seguire in parallelo tutti le possibili evoluzioni degli stati.

In conclusione, la differenza tra DFA e NFA risiede principalmente nel modo in cui le transizioni sono definite.

I DFA hanno una struttura più semplice e deterministica, mentre i NFA permettono una maggiore flessibilità con transizioni multiple e non determinate.

Ogni NFA può essere convertito in un DFA equivalente, sebbene il DFA risultante potrebbe essere più grande. Quindi, sono un buon punto di partenza per comprendere e costruire dei modelli di computazione più complessi.

La trasformazione da NFA a DFA

Ogni automa non deterministico NFA può essere trasformato in un automa deterministico DFA.

Questo significa che gli automi NFA e DFA accettano lo stesso linguaggio regolare.

Esempio

Consideriamo questo automa a stati finiti non deterministico NFA.

 

L'automa ha tre stati {q₀,q₁,q₂}, uno stato di ingresso in q₀ e uno stato di accettazione in q₂.

Per trasformarlo in un automa DFA procediamo con i seguenti passi:

1] Gli stati del DFA

Dato l'insieme degli stati Q={q₀,q₁,q₂} dell'automa NFA determiniamo l'insieme delle parti di Q come insieme degli stati del DFA.

$$ Q'= \{ \emptyset, \{ q_0 \}, \{ q_1 \}, \{ q_2 \}, \{ q_0, q_1 \}, \{ q_0, q_2 \}, \{ q_1, q_2 \}, \{ q_0, q_1, q_2 \} \} $$

Sono tutti i possibili sottoinsiemi degli stati che si possono raggiungere nel NFA.

2] Stato iniziale del DFA

Individuiamo lo stato di ingresso dell'automa DFA prendendo gli stati di ingresso dell'automa NFA che si ottengono prima ancora di aver valutato qualsiasi simbolo, considerando anche le transizioni vuote (ε).

In questo caso lo stato di ingresso è lo stesso $ q_0 $.

3] Stati di accettazione del DFA

Gli stati di accettazione del DFA sono tutti i sottoinsiemi di P(Q) che contengono lo stato di accettazione del NFA.

In questo caso lo stato di accettazione dell'automa NFA è lo stato q₂.

Quindi, gli stati di accettazione del DFA sono i sottoinsiemi che contengono q₂.

$$ F'= \{ \{ q_2 \}, \{ q_0, q_2 \}, \{ q_1, q_2 \}, \{ q_0, q_1, q_2 \} \} $$

4] Funzione di transizione del DFA

Costruiamo la funzione di transizione partendo dallo stato iniziale, valutando gli effetti di ogni simbolo x dell'alfabeto.

• Stato q₀
  Se x=0 la transizione successiva conduce a $$ δ(q_0,0)  = \{ q_0 \} $$ Se x=1 l'automa resta in q₀ oppure va in q₁ e automaticamente in q₂ tramite la stringa vuota. Pertanto l'automa si sposta nello stato {q₀,q₁,q₂} del DFA. $$ δ(q_0,1)  = \{ q_0, q_1, q_2 \} $$
  
• Stato {q₀,q₁,q₂}
  Se x=0 la transizione successiva conduce a  $$ δ(q_0,0) \cup δ(q_1,0) \cup δ(q_2,0) = \{q_0\} \cup \emptyset \cup \{q_2 \} = \{q_0, q_2 \} $$ Se x=1 la transizione successiva conduce a  $$ δ(q_0,1) \cup δ(q_1,1) \cup δ(q_2,1) = \{q_0, q_1, q_2 \} \cup \{q_2\} \cup \{q_2 \} = \{q_0, q_1, q_2 \} $$
  
• Stato {q₀,q₂}
  Se x=0 la transizione successiva conduce a  $$ δ(q_0,0) \cup δ(q_2,0)  = \{q_0\} \cup \{q_2 \} = \{q_0, q_2 \} $$ Se x=1 la transizione successiva conduce a  $$ δ(q_0,1) \cup δ(q_2,1) = \{q_0, q_1, q_2 \} \cup \{q_2\}  = \{q_0, q_1, q_2 \} $$
  

Il risultato finale è un automa a stati finiti deterministico.

Dove i doppi cerchi indicano gli stati di accettazione del DFA ovvero quelli che includono lo stato di accettazione q₂ dell'automa NFA.

La trasformazione da NFA a DFA

Ogni automa non deterministico NFA può essere trasformato in un automa deterministico DFA.

Questo significa che gli automi NFA e DFA accettano lo stesso linguaggio regolare.

Esempio

Consideriamo questo automa a stati finiti non deterministico NFA.

 

L'automa ha tre stati {q₀,q₁,q₂}, uno stato di ingresso in q₀ e uno stato di accettazione in q₂.

Per trasformarlo in un automa DFA procediamo con i seguenti passi:

1] Gli stati del DFA

Dato l'insieme degli stati Q={q₀,q₁,q₂} dell'automa NFA determiniamo l'insieme delle parti di Q come insieme degli stati del DFA.

$$ Q'= \{ \emptyset, \{ q_0 \}, \{ q_1 \}, \{ q_2 \}, \{ q_0, q_1 \}, \{ q_0, q_2 \}, \{ q_1, q_2 \}, \{ q_0, q_1, q_2 \} \} $$

Sono tutti i possibili sottoinsiemi degli stati che si possono raggiungere nel NFA.

2] Stato iniziale del DFA

Individuiamo lo stato di ingresso dell'automa DFA prendendo gli stati di ingresso dell'automa NFA che si ottengono prima ancora di aver valutato qualsiasi simbolo, considerando anche le transizioni vuote (ε).

In questo caso lo stato di ingresso è lo stesso $ q_0 $.

3] Stati di accettazione del DFA

Gli stati di accettazione del DFA sono tutti i sottoinsiemi di P(Q) che contengono lo stato di accettazione del NFA.

In questo caso lo stato di accettazione dell'automa NFA è lo stato q₂.

Quindi, gli stati di accettazione del DFA sono i sottoinsiemi che contengono q₂.

$$ F'= \{ \{ q_2 \}, \{ q_0, q_2 \}, \{ q_1, q_2 \}, \{ q_0, q_1, q_2 \} \} $$

4] Funzione di transizione del DFA

Costruiamo la funzione di transizione partendo dallo stato iniziale, valutando gli effetti di ogni simbolo x dell'alfabeto.

• Stato q₀
  Se x=0 la transizione successiva conduce a $$ δ(q_0,0)  = \{ q_0 \} $$ Se x=1 l'automa resta in q₀ oppure va in q₁ e automaticamente in q₂ tramite la stringa vuota. Pertanto l'automa si sposta nello stato {q₀,q₁,q₂} del DFA. $$ δ(q_0,1)  = \{ q_0, q_1, q_2 \} $$
  
• Stato {q₀,q₁,q₂}
  Se x=0 la transizione successiva conduce a  $$ δ(q_0,0) \cup δ(q_1,0) \cup δ(q_2,0) = \{q_0\} \cup \emptyset \cup \{q_2 \} = \{q_0, q_2 \} $$ Se x=1 la transizione successiva conduce a  $$ δ(q_0,1) \cup δ(q_1,1) \cup δ(q_2,1) = \{q_0, q_1, q_2 \} \cup \{q_2\} \cup \{q_2 \} = \{q_0, q_1, q_2 \} $$
  
• Stato {q₀,q₂}
  Se x=0 la transizione successiva conduce a  $$ δ(q_0,0) \cup δ(q_2,0)  = \{q_0\} \cup \{q_2 \} = \{q_0, q_2 \} $$ Se x=1 la transizione successiva conduce a  $$ δ(q_0,1) \cup δ(q_2,1) = \{q_0, q_1, q_2 \} \cup \{q_2\}  = \{q_0, q_1, q_2 \} $$
  

Il risultato finale è un automa a stati finiti deterministico.

Dove i doppi cerchi indicano gli stati di accettazione del DFA ovvero quelli che includono lo stato di accettazione q₂ dell'automa NFA.