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

m
Bot: Modifico: en:Nondeterministic finite-state machine; modifiche estetiche
m (s/NDFA/NFA)
m (Bot: Modifico: en:Nondeterministic finite-state machine; modifiche estetiche)
It is non-deterministic because it may encounter a situation where there are multiple transformations out of a state or it could transform to a new state without consuming any input symbols. For example, if it's in state 1, with the next input symbol an ''a'', it can move to state 2 without consuming any input symbols and can enter state 3 by consuming an ''a'' it is unable to determine the correct state to enter.
 
Transformations to new states without consuming an input symbol are called ''epsilon transitions''. They are usually labelled with the Greek letter εε.
 
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.
 
Un automa a stati finiti non deterministico è una quintupla,
(''S'', &Sigma;Σ, ''T'', ''s<sub>0</sub>'', ''A''), formata da:
* un insieme finito di stati (''S'')
* un insieme finito dei possibili simboli in input (&Sigma;Σ), chiamato alfabeto
* una relazione di transizione (''T'' : ''S'' &times;× &Sigma;Σ) &rarr; ''P''(''S'')).
* uno stato iniziale (''s<sub>0</sub>'' &isin; ''S'')
* un insieme di stati ''A'' di accettazione (''A'' &sube; ''S'')
 
Dato l'automa a stati finiti non deterministico '''M''' tale che '''M''' = (''S'', &Sigma;Σ, ''T'', ''s<sub>0</sub>'', ''A''), e ''X'' è una [[Stringa (formale)|stringa]] dell'alfabeto &Sigma;Σ. '''M''' accetta le stringhe ''X'' se esiste un rappresentazione di ''X'' nella forma ''x<sub>1</sub>x<sub>2</sub> ... x<sub>n</sub>'' (''x<sub>i</sub>'' &isin; &Sigma;Σ),
e una sequenza di stati ''r<sub>0</sub>,r<sub>1</sub>, ..., r<sub>n</sub>'', ''r<sub>i</sub>'' &isin; ''S'', concordate a queste definizioni:
# ''r<sub>0</sub>'' = ''s<sub>0</sub>''
# ''r<sub>i</sub>'' &isin; ''T''(''r<sub>i-1</sub>'', ''x<sub>i</sub> ''), for ''i'' = ''1, ..., n''
# ''r<sub>n</sub>'' &isin; ''A''.
 
La macchina parte dallo stato iniziale e legge un stringa. Attraverso la relazione di transizione T determina il prossimo/i stato/i di destinazione usando lo stato corrente e il simbolo appena letto. Se finisce in uno stato di accettazione la macchina accetta la stringa, altrimenti rifiuta la stringa. L'insieme di tutte le stringhe accettate dall'automa a stati finiti non deterministico è il linguaggio accettato dall'automa.
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.
 
''M'' = (''S'', &Sigma;Σ, ''T'', ''s<sub>0</sub>'', ''A'') dove
* &Sigma;Σ = {0, 1},
* ''S'' = {''S''<sub>0</sub>, ''S''<sub>1</sub>, ''S''<sub>2</sub>, ''S''<sub>3</sub>, ''S''<sub>4</sub>},
* ''s<sub>0</sub>'' = ''S''<sub>0</sub>,
|<center>'''0'''</center>
|<center>'''1'''</center>
|<center>'''&epsilon;ε'''</center>
|-
|<center>'''''S''<sub>0</sub>'''</center>
Il [[diagramma di stato]] per ''M'' è:
 
:[[ImmagineFile:NFAexample.svg]]
 
''M'' può essere visto come l'unione di due [[automa a stati finiti deterministico|automi a stati finiti deterministico]]: uno con gli stati{''S''<sub>2</sub>, ''S''<sub>1</sub>} e l'altro con gli stati {''S''<sub>3</sub>, ''S''<sub>4</sub>}.
 
===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 />
Ipotesi induttiva: <math>p\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 />
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}\epsilon-closure\left(r_{i}\right)</math>.
 
==Voci correlate==
* [[Automa a stati finiti]]
* [[Automa a stati finiti deterministico]]
* [[Automa probabilistico]]
 
{{Linguaggi formali e grammatiche}}
[[de:Nichtdeterministischer endlicher Automat]]
[[el:Μη ντετερμινιστικό πεπερασμένο αυτόματο]]
[[en:Nondeterministic finite -state machine]]
[[es:Autómata finito#Autómatas finitos no deterministas]]
[[fa:اتوماتون تعین‌نا‌پذیر متناهی]]
372 950

contributi