Differenze tra le versioni di "Automa a stati finiti non deterministico"

nessun oggetto della modifica
m (r2.7.2) (Bot: Modifico: en:Nondeterministic finite automaton)
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 <math>\epsilonvarepsilon</math>-transizioni ==
È possibile definire una variante degli automi a stati finiti non deterministici che permetta transizioni di stato spontanee, ossia transizioni su stringa vuota <math>\epsilonvarepsilon</math>. Per tali automi è sufficiente ridefinire la funzione di transizione come:
:<math>\delta\left(Q\times\left(\Sigma\cup\left\{ \epsilonvarepsilon\right\} \right)\right)\rightarrow\mathcal{P}\left(Q\right)</math>.
 
=== Funzione di chiusura su <math>\epsilonvarepsilon</math> ===
La funzione di chiusura su <math>\epsilonvarepsilon</math> <math>\epsilonvarepsilon-closure\left(\cdot\right)</math> si definisce induttivamente.<br />
Base: <math>q\in\epsilonvarepsilon-closure\left(q\right)</math>.<br />
Ipotesi induttiva: <math>p\in\epsilonvarepsilon-closure\left(q\right)</math>.<br />
Passo induttivo: <math>\delta\left(p,\epsilonvarepsilon\right)=\left\{ r_{1},...,r_{n}\right\} \subseteq\epsilonvarepsilon-closure\left(q\right)</math>.
 
=== Funzione di transizione estesa ===
La funzione di transizione estesa <math>\hat{\delta}\left(\cdot\right)</math> va ridefinita in termini di <math>\epsilonvarepsilon-closure</math> come segue:<br />
Base: <math>\hat{\delta}\left(q,\epsilonvarepsilon\right)=\epsilonvarepsilon-closure\left(q\right)</math>.<br />
Ipotesi induttiva: <math>\hat{\delta}\left(q,z\right)=\left\{ p_{1},...,p_{k}\right\}</math>.<br />
Passo induttivo: <math>\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}\epsilonvarepsilon-closure\left(r_{i}\right)</math>.
 
== Esempio ==
 
{| class="wikitable" align="center"
! || 0 || 1 || <math>\epsilonvarepsilon</math>
|-
| <math>S_0</math> || <math>\emptyset</math> || <math>\emptyset</math> || <math>\left \{ S_1, S_3 \right \}</math>