automa non deterministico a stati finiti (NFA)

Un automa non deterministico è un’automa che in qualsiai stato corrente può avere più stati prossimi.

Il non determinismo è una generalizzazione del determinismo, quindi ogni NFA è automaticamente un automa deterministico a stati finiti (DFA).

Un Non deterministic Finite state Automaton è una quintupla $N=(Q,\Sigma ,\delta ,q_0,f)$, dove $Q,\Sigma ,q_0,F$ corrispondono a quelle del DFA, mentre la differenza della funzione di transizione $\delta$ è che da ogni stato del NFA si può transitare verso più stati.

$$\delta :Q\times (\underset{\Sigma \cup \{\epsilon \}}{\underbrace{{\Sigma }_{\epsilon }}})\to \underset{\text{insieme delle parti}}{\underbrace{\mathcal{P}(Q)}}$$

• $\mathcal{P}(Q)$ è l’insieme delle parti di $Q$.
• $\epsilon$ è un’etichetta degli archi che procedono da uno stato al prossimo automaticamente, senza dover ricevere un input $\in \Sigma$.

Dal punto di vista dei cammini di computazione, i DFA ne compiono solo uno, e alla fine rifiutano o accettano la stringa in input. Invece gli NFA, i cammini di computazione possono “sdoppiarsi”: a ogni transizione da uno a $n$ stati, l’automa crea copie di se stesso, le quali continuano l’esecuzione in parallelo.

I linguaggi riconosciuti da un NFA sono quelli le cui stringhe sono riconosciute da almeno un suo cammino di computazione.

Gli NFA possono avere degli $\epsilon$-archi, cioè archi che portano da uno stato all’altro a prescindere dall’input, cioè sempre e in automatico.

• Concetto di configurazione

Esempio

Esempio di input $w=10110$

Esecuzione:

Dimostrazione che i linguaggi riconosciuti dagli NFA sono gli stessi riconosciuti dai DFA, cioè i linguaggi regolari

Due automi si dicono equivalenti se riconoscono lo stesso linguaggio.

Teorema: I DFA e i NFA riconoscono gli stessi linguaggi, cioè i linguaggi regolari. $\mathcal{L}(DFA)=\mathcal{L}(NFA)=\text{REG}$

Dimostrazione:

1. Banalmente $\mathcal{L}(DFA)\subseteq \mathcal{L}(NFA)$ perchè, per definizione, un DFA è un caso speciale di un NFA.
2. Ora bisogna dimostrare $\mathcal{L}(NFA)\subseteq \mathcal{L}(DFA)$.
   1. Sia $N=(Q_N,\Sigma ,{\delta }_N,q_0^N,F_N)$ un NFA tale che $L(N)=A$. Devo mostrare che esiste un DFA $M$ tale che $L(M)=A$. Per costruire il DFA $M$ bisogna unire tutti i possibili cammini di computazione esplorati dal NFA $N$ in un singolo DFA.
   2. Quindi $Q_M=\mathcal{P}(Q_N)$, cioè quando $Q_N$ sta in più stati contemporaneamente, $Q_M$ è in uno solo stato $\in \mathcal{P}(Q_N)$. Ogni elemento di questo insieme (delle parti) rappresenta più stati di $Q_N$ allo stesso tempo.
   3. Definiamo i componenti della tupla di $M$ che ci mancano:
      1. $q_0$: Per lo stato iniziale vale $q_0^M=\{q_0^N\}$.
      2. $F_M$: Quand’è che $N$ accetta una stringa? Quando almeno uno dei suoi cammini la accetta. Di conseguenza, $M$ deve accettare una stringa quando almeno uno dei cammini di $N$ la accetta. $F_M=\{R\in Q_M:R\cap F_N\ne \varnothing \}$ (cioè $R$ contiene almeno uno stato finale di $F_N$).
      3. ${\delta }_M:$ la funzione di transizione deve essere definita come ${\delta }_M:Q_M\times \Sigma \to Q_M$. Inoltre ogni stato di $N$ contenuto all’interno di uno stato di $M$ deve puntare all’insieme dato dall’unione di tutti gli stati di $N$ raggiungibili da esso, cioè ${\delta }_M(R,a)={\bigcup }_{r\in R}{\delta }_N(r,a)$.
   4. Aggiungiamo gli $\epsilon$-archi. Cosa cambia? (nota: $E(\text{stato})$ è l’insieme di stati di $N$ raggiungibili tramite 0 o più $\epsilon$ archi).
      1. Definiamo $q_0^{\prime }=E(\{q_0^N\})$.
      2. Definiamo ${\delta }_M^{\prime }(R,a)={\bigcup }_{r\in R}E({\delta }_N(r,a))$
   5. Abbiamo ottenuto il DFA $$M=\left(Q_M=\mathcal{P}(Q_N),\Sigma ,{\delta }_M^{\prime }=\bigcup _{r\in R}E({\delta }_N(r,a)),q_0^M=E(\{q_0^N\}),F_M=\{R\in Q_M:R\cap F_N\ne \varnothing \}\right)$$ Equivalente al NFA $M$.

Esercizio

1. Definizione degli stati $Q_m$

$$Q_m=\{q_{\varnothing },q_{\{1\}},q_{\{2\}},q_{\{3\}},q_{\{1,2\}},q_{\{2,3\}},q_{\{1,3\}},q_{\{1,2,3\}}\}$$

2. Definizione dello stato iniziale $q_0^M$

$$q_0^M=q_{1,3}$$

3. Definizione degli stati finali $F_M$

$$F_M=\{q_{\{1\}},q_{\{1,2\}},q_{\{1,3\}},q_{\{1,2,3\}}\}$$

4. Definizione della funzione di transizione $S_M$

$$S_M:Q_M\times \Sigma \to Q_M$$

Considero i diversi casi:

• Nello stato $q_1$:
  • se $N$ legge $b$ può transitare in $q_2$, cioè $S_M(q_{\{1\}},b)=q_{\{2\}}$.
  • se $N$ legge $a$ va in uno stato pozzo, cioè $S_M(q_{\{1\}},a)=q_{\varnothing }$.
• Nello stato $q_2$:
  • se $N$ legge $a$ può transitare in $q_2$ e $q_3$, cioè $S_M(q_{\{2\}},a)=q_{\{2,3\}}$.
  • se $N$ legge $b$ può transitare in $q_3$, cioè $S_M(q_{\{2\}},b)=q_{\{3\}}$.
• Nello stato $q_3$:
  • se $N$ legge $a$ può transitare in $q_1$, cioè $S_M(q_{\{3\}},a)=q_{\{1,3\}}$. Nell’insieme c’è anche $q_3$ perché si prende immediatamente l’$\epsilon$-arco da $q_1$.
  • se $N$ legge $b$ va in uno stato pozzo, cioè $S_M(q_{\{1\}},b)=q_{\varnothing }$.

N.B.: Per un qualsiasi stato $q_n$ si deve MAI definire $S_M(q_n,\epsilon )$, ma accorpare la destinazione dell’$\epsilon$-arco nella $S_M$ degli altri input, cioè $S_M(q_n,{\text{input}}_k)$.

Disegno del DFA $M$