Automa a stati finiti non deterministico: differenze tra le versioni

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

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 />

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

! || 0 || 1 || <math>\epsilonvarepsilon</math>