Automa a stati finiti non deterministico

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

Definizione formale

Un automa a stati finiti non deterministico è una quintupla, (S, Σ, T, s₀, A), formata da:

• un insieme finito di stati (S)
• un insieme finito dei possibili simboli in input (Σ), chiamato alfabeto
• una relazione di transizione (T : S × Σ) → P(S)).
• uno stato iniziale (s₀ ∈ S)
• un insieme di stati A di accettazione (A ⊆ S)

Dato l'automa a stati finiti non deterministico M tale che M = (S, Σ, T, s₀, A), e X è una stringa dell'alfabeto Σ. M accetta le stringhe X se esiste un rappresentazione di X nella forma x₁x₂ ... x_n (x_i ∈ Σ), e una sequenza di stati r₀,r₁, ..., r_n, r_i ∈ S, concordate a queste definizioni:

1. r₀ = s₀
2. r_i ∈ T(r_i-1, x_i ), for i = 1, ..., n
3. r_n ∈ A.

La macchina parte dallo stato iniziale e legge un stringa. Attraverso la relazione di transizione T determina il prossimo/i stato/i di destinazione usando lo stato corrente e il simbolo appena letto. Se finisce in uno stato di accettazione la macchina accetta la stringa, altrimenti rifiuta la stringa. L'insieme di tutte le stringhe accettate dall'automa a stati finiti non deterministico è il linguaggio accettato dall'automa.

Il linguaggio accettato da questo tipo di automa è un linguaggio regolare.

Equivalenza tra automa non deterministico e deterministico

Per ogni automa a stati finiti non deterministico può essere trovato un automa a stati finiti deterministico che accetta lo stesso linguaggio. Quindi è possibile convertire un automa a stati finiti non deterministico in uno deterministico per realizzare una macchina più semplice; quest'operazione può essere effettuata utilizzando la costruzione dei sottoinsiemi.

Esempio

Il seguente esempio mostra un automa a stati finiti non deterministico M, con alfabeto binario, il quale determina se l'input contiene un numero pari di zero o un numero pari di uno.

M = (S, Σ, T, s₀, A) dove

• Σ = {0, 1},
• S = {S₀, S₁, S₂, S₃, S₄},
• s₀ = S₀,
• A = {S₁, S₃}, e
• La funzione di transizione T può essere definita da questa tabella di transizione di stato:

	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

Il diagramma di stato per M è:

M può essere visto come l'unione di due automi a stati finiti deterministico: uno con gli stati{S₂, S₁} e l'altro con gli stati {S₃, S₄}.

Il linguaggio di M può essere descritto da un linguaggio regolare attraverso la seguente espressione regolare:

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

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

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

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

Funzione di chiusura su $\epsilon$

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

Funzione di transizione estesa

La funzione di transizione estesa ${\hat {\delta }}\left(\cdot \right)$ va ridefinita in termini di $\epsilon -closure$ come segue:
Base: ${\hat {\delta }}\left(q,\epsilon \right)=\epsilon -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}\epsilon -closure\left(r_{i}\right)$.

Voci correlate

• Automa a stati finiti
• Automa a stati finiti deterministico
• Automa probabilistico