Automa a stati finiti non deterministico: differenze tra le versioni
m s/NDFA/NFA |
m Bot: Modifico: en:Nondeterministic finite-state machine; modifiche estetiche |
||
Riga 9: | Riga 9: | ||
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. |
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 |
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. |
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. |
||
Riga 16: | Riga 16: | ||
Un automa a stati finiti non deterministico è una quintupla, |
Un automa a stati finiti non deterministico è una quintupla, |
||
(''S'', |
(''S'', Σ, ''T'', ''s<sub>0</sub>'', ''A''), formata da: |
||
* un insieme finito di stati (''S'') |
* un insieme finito di stati (''S'') |
||
* un insieme finito dei possibili simboli in input ( |
* un insieme finito dei possibili simboli in input (Σ), chiamato alfabeto |
||
* una relazione di transizione (''T'' : ''S'' |
* una relazione di transizione (''T'' : ''S'' × Σ) → ''P''(''S'')). |
||
* uno stato iniziale (''s<sub>0</sub>'' |
* uno stato iniziale (''s<sub>0</sub>'' ∈ ''S'') |
||
* un insieme di stati ''A'' di accettazione (''A'' |
* un insieme di stati ''A'' di accettazione (''A'' ⊆ ''S'') |
||
Dato l'automa a stati finiti non deterministico '''M''' tale che '''M''' = (''S'', |
Dato l'automa a stati finiti non deterministico '''M''' tale che '''M''' = (''S'', Σ, ''T'', ''s<sub>0</sub>'', ''A''), e ''X'' è una [[Stringa (formale)|stringa]] dell'alfabeto Σ. '''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>'' ∈ Σ), |
||
e una sequenza di stati ''r<sub>0</sub>,r<sub>1</sub>, ..., r<sub>n</sub>'', ''r<sub>i</sub>'' |
e una sequenza di stati ''r<sub>0</sub>,r<sub>1</sub>, ..., r<sub>n</sub>'', ''r<sub>i</sub>'' ∈ ''S'', concordate a queste definizioni: |
||
# ''r<sub>0</sub>'' = ''s<sub>0</sub>'' |
# ''r<sub>0</sub>'' = ''s<sub>0</sub>'' |
||
# ''r<sub>i</sub>'' |
# ''r<sub>i</sub>'' ∈ ''T''(''r<sub>i-1</sub>'', ''x<sub>i</sub> ''), for ''i'' = ''1, ..., n'' |
||
# ''r<sub>n</sub>'' |
# ''r<sub>n</sub>'' ∈ ''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. |
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. |
||
Riga 40: | Riga 40: | ||
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. |
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'', |
''M'' = (''S'', Σ, ''T'', ''s<sub>0</sub>'', ''A'') dove |
||
* |
* Σ = {0, 1}, |
||
* ''S'' = {''S''<sub>0</sub>, ''S''<sub>1</sub>, ''S''<sub>2</sub>, ''S''<sub>3</sub>, ''S''<sub>4</sub>}, |
* ''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>, |
* ''s<sub>0</sub>'' = ''S''<sub>0</sub>, |
||
Riga 50: | Riga 50: | ||
|<center>'''0'''</center> |
|<center>'''0'''</center> |
||
|<center>'''1'''</center> |
|<center>'''1'''</center> |
||
|<center>''' |
|<center>'''ε'''</center> |
||
|- |
|- |
||
|<center>'''''S''<sub>0</sub>'''</center> |
|<center>'''''S''<sub>0</sub>'''</center> |
||
Riga 80: | Riga 80: | ||
Il [[diagramma di stato]] per ''M'' è: |
Il [[diagramma di stato]] per ''M'' è: |
||
:[[ |
:[[File: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>}. |
''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>}. |
||
Riga 92: | Riga 92: | ||
===Funzione di chiusura su <math>\epsilon</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> |
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> |
Base: <math>q\in\epsilon-closure\left(q\right)</math>.<br /> |
||
Ipotesi induttiva: <math>p\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>. |
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=== |
===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> |
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> |
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> |
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>. |
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== |
==Voci correlate== |
||
*[[Automa a stati finiti]] |
* [[Automa a stati finiti]] |
||
*[[Automa a stati finiti deterministico]] |
* [[Automa a stati finiti deterministico]] |
||
*[[Automa probabilistico]] |
* [[Automa probabilistico]] |
||
{{Linguaggi formali e grammatiche}} |
{{Linguaggi formali e grammatiche}} |
||
Riga 115: | Riga 115: | ||
[[de:Nichtdeterministischer endlicher Automat]] |
[[de:Nichtdeterministischer endlicher Automat]] |
||
[[el:Μη ντετερμινιστικό πεπερασμένο αυτόματο]] |
[[el:Μη ντετερμινιστικό πεπερασμένο αυτόματο]] |
||
[[en:Nondeterministic finite |
[[en:Nondeterministic finite-state machine]] |
||
[[es:Autómata finito#Autómatas finitos no deterministas]] |
[[es:Autómata finito#Autómatas finitos no deterministas]] |
||
[[fa:اتوماتون تعینناپذیر متناهی]] |
[[fa:اتوماتون تعینناپذیر متناهی]] |
Versione delle 19:48, 19 mar 2010
Nella teoria del calcolo, un automa a stati finiti non deterministico (NFA in inglese) è una macchina a stati finiti dove per ogni coppia stato-simbolo in input ci possono essere più stati di destinazione.
Definizione formale
Un automa a stati finiti non deterministico è una quintupla, (S, Σ, T, s0, A), formata da:
- un insieme finito di stati (S)
- un insieme finito dei possibili simboli in input (Σ), chiamato alfabeto
- una relazione di transizione (T : S × Σ) → P(S)).
- uno stato iniziale (s0 ∈ S)
- un insieme di stati A di accettazione (A ⊆ S)
Dato l'automa a stati finiti non deterministico M tale che M = (S, Σ, T, s0, A), e X è una stringa dell'alfabeto Σ. M accetta le stringhe X se esiste un rappresentazione di X nella forma x1x2 ... xn (xi ∈ Σ), e una sequenza di stati r0,r1, ..., rn, ri ∈ S, concordate a queste definizioni:
- r0 = s0
- ri ∈ T(ri-1, xi ), for i = 1, ..., n
- rn ∈ 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 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.
M = (S, Σ, T, s0, A) dove
- Σ = {0, 1},
- S = {S0, S1, S2, S3, S4},
- s0 = S0,
- A = {S1, S3}, e
- La funzione di transizione T può essere definita da questa tabella di transizione di stato:
Il diagramma di stato per M è:
M può essere visto come l'unione di due automi a stati finiti deterministico: uno con gli stati{S2, S1} e l'altro con gli stati {S3, S4}.
Il linguaggio di M può essere descritto da un linguaggio regolare attraverso la seguente espressione regolare:
Automa a stati finiti non deterministico con -transizioni
È possibile definire una variante degli automi a stati finiti non deterministici che permetta transizioni di stato spontanee, ossia transizioni su stringa vuota . Per tali automi è sufficiente ridefinire la funzione di transizione come:
- .
Funzione di chiusura su
La funzione di chiusura su si definisce induttivamente.
Base: .
Ipotesi induttiva: .
Passo induttivo: .
Funzione di transizione estesa
La funzione di transizione estesa va ridefinita in termini di come segue:
Base: .
Ipotesi induttiva: .
Passo induttivo: .