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

m
(→‎Automa a stati finiti non deterministico con \varepsilon-transizioni: i caratteri unicode nel titolo non sono un idea saggia, convertito \varepsilon in Epsilon)
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 Epsilonepsilon-transizioni ==
È possibile definire una variante degli automi a stati finiti non deterministici che permetta transizioni di stato spontanee, ossia transizioni su stringa vuota <math>\varepsilon</math>. Per tali automi è sufficiente ridefinire la funzione di transizione come:
:<math>\delta\left(Q\times\left(\Sigma\cup\left\{ \varepsilon\right\} \right)\right)\rightarrow\mathcal{P}\left(Q\right)</math>.