Indietro

ⓘ Automa a stati finiti non deterministico




Automa a stati finiti non deterministico
                                     

ⓘ Automa a stati finiti non deterministico

Nella teoria del calcolo, un automa a stati finiti non deterministico è 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.

                                     

1. Definizione formale

Un automa a stati finiti non deterministico è una quintupla A = ⟨ Σ, S, δ, s 0, F ⟩ {\displaystyle {\mathcal {A}}=\left\langle \Sigma,S,\delta,s_{0},F\right\rangle } con:

  • F ⊆ S {\displaystyle F\subseteq S} insieme di stati finali
  • Σ = { a 0, a 1, …, a n } {\displaystyle \Sigma =\{a_{0},a_{1},\ldots,a_{n}\}} insieme finito di simboli chiamato alfabeto
  • s 0 ∈ S {\displaystyle s_{0}\in S} stato iniziale
  • S = { s 0, s 1, …, s m } {\displaystyle S=\{s_{0},s_{1},\ldots,s_{m}\}} insieme finito di stati
  • δ: S × Σ → P S {\displaystyle \delta:S\times \Sigma \to PS} funzione di transizione, dove P S {\displaystyle PS} è linsieme delle parti di S

Dato un NFA A = ⟨ Σ, S, δ, s 0, F ⟩ {\displaystyle {\mathcal {A}}=\left\langle \Sigma,S,\delta,s_{0},F\right\rangle } ed una stringa w ∈ Σ ∗ {\displaystyle w\in \Sigma ^{*}}, A accetta la stringa w = x 1 x 2 ⋯ x n {\displaystyle w=x_{1}x_{2}\cdots x_{n}} con x i ∈ Σ {\displaystyle x_{i}\in \Sigma } se esiste una sequenza di stati R = { r 0, r 1, ⋯, r n } {\displaystyle R=\left\{r_{0},r_{1},\cdots,r_{n}\right\}} tale che:

  • r 0 = s 0 {\displaystyle r_{0}=s_{0}}
  • δ r i, x n ∩ F ≠ ∅ {\displaystyle \delta r_{i},x_{n}\cap F\neq \emptyset }
  • δ r i, x i ∈ R {\displaystyle \delta r_{i},x_{i}\in R}

La macchina parte dallo stato iniziale e legge una stringa. Attraverso la relazione di transizione δ {\displaystyle \delta } si determina lo stato o gli stati di destinazione in base allo stato corrente ed al simbolo letto. Se dopo aver letto lultimo simbolo la macchina si trova in almeno uno degli stati appartenenti ad F, la macchina accetta la stringa, altrimenti la rifiuta. Linsieme di tutte le stringhe accettate dallautoma a stati finiti non deterministico è il linguaggio accettato dallautoma.

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

                                     

2. 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.

                                     

3. 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 ε {\displaystyle \varepsilon }. Per tali automi è sufficiente ridefinire la funzione di transizione come:

δ Q × Σ ∪ { ε }) → P Q {\displaystyle \delta \leftQ\times \left\Sigma \cup \left\{\varepsilon \right\}\right\right)\rightarrow {\mathcal {P}}\leftQ\right}.
                                     

3.1. Automa a stati finiti non deterministico con epsilon-transizioni Funzione di chiusura su ε {\displaystyle \varepsilon }

La funzione di chiusura su ε {\displaystyle \varepsilon } ε − c l o s u r e ⋅ {\displaystyle \varepsilon -closure\left\cdot \right} si definisce induttivamente. Base: q ∈ ε − c l o s u r e q {\displaystyle q\in \varepsilon -closure\leftq\right}. Ipotesi induttiva: p ∈ ε − c l o s u r e q {\displaystyle p\in \varepsilon -closure\leftq\right}. Passo induttivo: δ p, ε = { r 1., r n } ⊆ ε − c l o s u r e q {\displaystyle \delta \leftp,\varepsilon \right=\left\{r_{1}.,r_{n}\right\}\subseteq \varepsilon -closure\leftq\right}.

                                     

3.2. Automa a stati finiti non deterministico con epsilon-transizioni Funzione di transizione estesa

La funzione di transizione estesa δ ^ ⋅ {\displaystyle {\hat {\delta }}\left\cdot \right} va ridefinita in termini di ε − c l o s u r e {\displaystyle \varepsilon -closure} come segue: Base: δ ^ q, ε = ε − c l o s u r e q {\displaystyle {\hat {\delta }}\leftq,\varepsilon \right=\varepsilon -closure\leftq\right}. Ipotesi induttiva: δ ^ q, z = { p 1., p k } {\displaystyle {\hat {\delta }}\leftq,z\right=\left\{p_{1}.,p_{k}\right\}}. Passo induttivo: ω = z a ∧ ⋃ i = 1 k δ p i, a = { r 1., r m } ⇒ δ ^ q, ω = ⋃ i = 1 m ε − c l o s u r e r i {\displaystyle \omega =za\wedge \bigcup _{i=1}^{k}\delta \leftp_{i},a\right=\left\{r_{1}.,r_{m}\right\}\Rightarrow {\hat {\delta }}\leftq,\omega \right=\bigcup _{i=1}^{m}\varepsilon -closure\leftr_{i}\right}.

                                     

4. Esempio

Il seguente esempio mostra un automa a stati finiti non deterministico A {\displaystyle A}, sullalfabeto binario, in grado di determinare se la stringa in input contiene un numero pari di zero o di uno.

A = ⟨ Σ, S, δ, s 0, F ⟩ {\displaystyle {\mathcal {A}}=\left\langle \Sigma,S,\delta,s_{0},F\right\rangle } dove

  • La funzione di transizione δ {\displaystyle \delta } è definita dalla seguente tabella di transizione
  • F = { S 1, S 3 } {\displaystyle F=\left\{S_{1},S_{3}\right\}}
  • S = { S 0, S 1, S 2, S 3, S 4 } {\displaystyle S=\left\{S_{0},S_{1},S_{2},S_{3},S_{4}\right\}}
  • Σ = { 0, 1 } {\displaystyle \Sigma =\left\{0.1\right\}}
  • s 0 = S 0 {\displaystyle s_{0}=S_{0}}

È inoltre importante far notare che A {\displaystyle A} può essere ricavato dallunione di due automi a stati finiti deterministici i cui stati sono rispettivamente { S 1, S 2 } {\displaystyle \left\{S_{1},S_{2}\right\}} e { S 3, S 4 } {\displaystyle \left\{S_{3},S_{4}\right\}}. Il linguaggio regolare riconosciuto dallautoma è inoltre esprimibile tramite lespressione regolare

1 ∗ 01 ∗ 01 ∗ ∗) + 0 ∗ 10 ∗ 10 ∗ ∗) {\displaystyle 1^{*}01^{*}01^{*}^{*})+0^{*}10^{*}10^{*}^{*})}