Automa a stati finiti non deterministico: differenze tra le versioni
m Bot: Aggiungo: zh:非确定有限状态自动机 |
m Bot: Correzione di uno o più errori comuni |
||
Riga 88: | Riga 88: | ||
==Automa a stati finiti non deterministico con <math>\epsilon</math>-transizioni== |
==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 \epsilon. 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>. |
:<math>\delta\left(Q\times\left(\Sigma\cup\left\{ \epsilon\right\} \right)\right)\rightarrow\mathcal{P}\left(Q\right)</math>. |
||
Versione delle 19:20, 7 lug 2008
Nella teoria del calcolo, un automa a stati finiti non deterministico (NDFA 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 \epsilon. 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: .