Automa a stati finiti non deterministico

Nella teoria del calcolo, un automa a stati finiti non deterministico (in inglese nondeterministic finite automaton, NFA) è una macchina a stati finiti dove per ogni coppia stato-simbolo in input possono esservi più stati di destinazione.

Al contrario degli automi a stati finiti deterministici, gli NFA possono cambiare stato indipendentemente dal simbolo letto, tramite epsilon-transizioni. Gli automi che presentano questo tipo di transizioni sono anche detti ε-NFA.

Definizione formale

Un automa a stati finiti non deterministico è una quintupla $\mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle$ con:

• $\Sigma = \{a_0, a_1, \ldots, a_n\}$ insieme finito di simboli chiamato alfabeto
• $S = \{s_0, s_1, \ldots, s_m\}$ insieme finito di stati
• $\delta : S \times \Sigma \to P(S)$ funzione di transizione, dove $P(S)$ è l'insieme delle parti di S
• $s_0 \in S$ stato iniziale
• $F \subseteq S$ insieme di stati finali

Dato un NFA $\mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle$ ed una stringa $w \in \Sigma^{*}$, A accetta la stringa $w = x_1 x_2 \cdots x_n$ con $x_i \in \Sigma$ se esiste una sequenza di stati $R = \left \{ r_0, r_1, \cdots, r_n \right \}$ tale che:

1. $r_0 = s_0$
2. $\delta(r_i, x_i) \in R$
3. $\delta(r_i, x_n) \cap F \ne \emptyset$

La macchina parte dallo stato iniziale e legge una stringa. Attraverso la relazione di transizione $\delta$ si determina lo stato o gli stati di destinazione in base allo stato corrente ed al simbolo letto. Se dopo aver letto l'ultimo simbolo la macchina si trova in almeno uno degli stati appartenenti ad F, la macchina accetta la stringa, altrimenti la rifiuta. L'insieme di tutte le stringhe accettate dall'automa a stati finiti non deterministico è il linguaggio accettato dall'automa.

Il linguaggio accettato dagli automi a stati finiti non deterministico è un linguaggio regolare.

Equivalenza tra automa non deterministico e deterministico

Per ogni automa a stati finiti non deterministico è possibile costruire un automa a stati finiti deterministico in grado di riconoscere lo stesso linguaggio utilizzando la costruzione dei sottoinsiemi.

Automa a stati finiti non deterministico con $\varepsilon$-transizioni

È possibile definire una variante degli automi a stati finiti non deterministici che permetta transizioni di stato spontanee, ossia transizioni su stringa vuota $\varepsilon$. Per tali automi è sufficiente ridefinire la funzione di transizione come:

$\delta\left(Q\times\left(\Sigma\cup\left\{ \varepsilon\right\} \right)\right)\rightarrow\mathcal{P}\left(Q\right)$.

Funzione di chiusura su $\varepsilon$

La funzione di chiusura su $\varepsilon$ $\varepsilon-closure\left(\cdot\right)$ si definisce induttivamente.
Base: $q\in\varepsilon-closure\left(q\right)$.
Ipotesi induttiva: $p\in\varepsilon-closure\left(q\right)$.
Passo induttivo: $\delta\left(p,\varepsilon\right)=\left\{ r_{1},...,r_{n}\right\} \subseteq\varepsilon-closure\left(q\right)$.

Funzione di transizione estesa

La funzione di transizione estesa $\hat{\delta}\left(\cdot\right)$ va ridefinita in termini di $\varepsilon-closure$ come segue:
Base: $\hat{\delta}\left(q,\varepsilon\right)=\varepsilon-closure\left(q\right)$.
Ipotesi induttiva: $\hat{\delta}\left(q,z\right)=\left\{ p_{1},...,p_{k}\right\}$.
Passo induttivo: $\omega=za\wedge\bigcup_{i=1}^{k}\delta\left(p_{i},a\right)=\left\{ r_{1},...,r_{m}\right\} \Rightarrow\hat{\delta}\left(q,\omega\right)=\bigcup_{i=1}^{m}\varepsilon-closure\left(r_{i}\right)$.

Esempio

Il seguente esempio mostra un automa a stati finiti non deterministico $A$, sull'alfabeto binario, in grado di determinare se la stringa in input contiene un numero pari di zero o di uno.

$\mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle$ dove

• $\Sigma = \left \{ 0, 1 \right \}$
• $S = \left \{ S_0, S_1, S_2, S_3, S_4 \right \}$
• $s_0 = S_0$
• $F = \left \{ S_1, S_3 \right \}$
• La funzione di transizione $\delta$ è definita dalla seguente tabella di transizione:

	0	1	$\varepsilon$
$S_0$	$\emptyset$	$\emptyset$	$\left \{ S_1, S_3 \right \}$
$S_1$	$\left \{ S_2 \right \}$	$\left \{ S_1 \right \}$	$\emptyset$
$S_2$	$\left \{ S_1 \right \}$	$\left \{ S_2 \right \}$	$\emptyset$
$S_3$	$\left \{ S_3 \right \}$	$\left \{ S_4 \right \}$	$\emptyset$
$S_4$	$\left \{ S_4 \right \}$	$\left \{ S_3 \right \}$	$\emptyset$

Automa a stati finiti dell'esempio

È inoltre importante far notare che $A$ può essere ricavato dall'unione di due automi a stati finiti deterministici i cui stati sono rispettivamente $\left \{ S_1, S_2 \right \}$ e $\left \{ S_3, S_4 \right \}$. Il linguaggio regolare riconosciuto dall'automa è inoltre esprimibile tramite l'espressione regolare

$(1^*(01^*01^*)^*) \cup (0^*(10^*10^*)^*)$

Bibliografia

• nondeterministic finite automaton in Academic Press Dictionary of Science and Technology (in inglese), Oxford, Elsevier Science & Technology, 1992.
• automata theory in Encyclopedia of Computer Science (in inglese), Hoboken, Wiley, 2003.
• John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman, Finite Automata in Introduction to Automata Theory, Languages, and Computation (in inglese), Addison Wesley, 15 luglio 2006. 978-0321462251
• Martin Davis; Ron Sigal; Elaine J. Weyuker, Finite Automata in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (in inglese), Morgan Kaufmann, 17 febbraio 1994. 978-0122063824

Voci correlate

• Automa a stati finiti
• Automa a stati finiti deterministico
• Costruzione dei sottoinsiemi
• Linguaggio regolare
• Grammatica regolare
• Espressione regolare

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica	Linguaggio	Automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Dipendente dal contesto	Dipendente dal contesto	Automa lineare
Tipo-2	Libera dal contesto	Libero dal contesto	Automa a pila ND
Tipo-3	Regolare	Regolare	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante.

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica