automa non deterministico a stati finiti (NFA)

Un Non deterministic Finite state Automaton è una tupla $N=(Q,\Sigma ,\delta ,q_0,f)$, dove $Q,\Sigma ,q_0,F$ corrispondono a quelle dell’automa a stati finiti (DFA), mentre $\delta$ cambia da ogni stato del NFA si può transitare verso più stati.

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

$\mathcal{P}(Q)$ è l’insieme delle parti di $Q$.

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

Ipotesi: $\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=L(N)$. Devo mostrare che esiste un DFA $M=(Q_M,\Sigma ,{\delta }_M,q_0^M,F_M)$ tale che $L(M)=L$. Praticamente bisogna unire tutti i possibili cammini di computazione esplorati dal NFA 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 stato $\in \mathcal{P}(Q_N)$ che 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 \}$ ($R$ contiene almeno uno stato finale di $F_N$).
      3. ${\delta }_M:$ il dominio e il codominio la funzione di transizione deve essere definiti come ${\delta }_M:Q_M\times \Sigma \to Q_M$. Inoltre ogni stato di $N$ contenuto all’interno di uno stato di $M$ deve portare 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 $\epsilon$ archi)
      1. $q_0^M=E(\{q_0^N\})$
      2. ${\delta }_M(R,a)={\bigcup }_{r\in R}E({\delta }_N(r,a))$

Esercizio

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\}}\}$$

Definizione dello stato iniziale $q_0^M$

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

Definizione degli stati finali $F_M$

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

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 NFA $M$