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

m
[r2.5.2] Bot: Modifico: uk:Недетермінований автомат; modifiche estetiche
m ([r2.5.2] Bot: Modifico: uk:Недетермінований автомат; modifiche estetiche)
When the last input symbol is consumed the NFA accepts if and only if there is ''some'' set of transitions it could make that will take it to an accepting state. Equivalently, it rejects iff no matter what choices it makes it would not end in an accepting state.
-->
== Definizione formale ==
 
Un automa a stati finiti non deterministico è una quintupla,
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.
:<math>(1^*(01^*01^*)^*) \cup (0^*(10^*10^*)^*) </math>
 
== Automa a stati finiti non deterministico con <math>\epsilon</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>\epsilon</math>. Per tali automi è sufficiente ridefinire la funzione di transizione come:
:<math>\delta\left(Q\times\left(\Sigma\cup\left\{ \epsilon\right\} \right)\right)\rightarrow\mathcal{P}\left(Q\right)</math>.
 
=== Funzione di chiusura su <math>\epsilon</math> ===
La funzione di chiusura su <math>\epsilon</math> <math>\epsilon-closure\left(\cdot\right)</math> si definisce induttivamente.<br />
Base: <math>q\in\epsilon-closure\left(q\right)</math>.<br />
Passo induttivo: <math>\delta\left(p,\epsilon\right)=\left\{ r_{1},...,r_{n}\right\} \subseteq\epsilon-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>\epsilon-closure</math> come segue:<br />
Base: <math>\hat{\delta}\left(q,\epsilon\right)=\epsilon-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}\epsilon-closure\left(r_{i}\right)</math>.
 
== Voci correlate ==
* [[Automa a stati finiti]]
* [[Automa a stati finiti deterministico]]
[[sh:Nedeterministički konačni automat]]
[[sr:Недетерминистички коначни аутомат]]
[[uk:Недетермінований автомат]]
[[uk:Автомат недетермінований]]
[[zh:非确定有限状态自动机]]
372 950

contributi