Automa a stati finiti deterministico
Da Wikipedia, l'enciclopedia libera.
Nella teoria del calcolo, un automa a stati finiti deterministico o deterministic finite automaton (DFA) è un'automa a stati finiti dove per ogni coppia di stato e simbolo in ingresso c'è una ed una sola transizione allo stato successivo.
Indice |
[modifica] Definizione Formale
Un DFA è una 5-tupla, (S, Σ, T, s, A), consiste di
- un insieme finito di stati (S)
- un insieme finito di simboli chiamato alfabeto (Σ)
- una funzione di transizione (T : S × Σ → S)
- uno stato iniziale (s ∈ S)
- un insieme di stati di accettazione (A ⊆ S)
Dato M sia una DFA tale che M = (S, Σ, T, s, A), e X = x0x1 ... xn sia una stringa appartenente all'alfabeto Σ. M accetta la stringa X se esiste una sequenza di stati, r0,r1, ..., rn, in S con le seguenti condizioni:
- r0 = s
- ri+1 = T(ri, xi), per i = 0, ..., n-1
- rn ∈ A.
Come mostrato nella prima condizione, l'automa parte dallo stato iniziale s. La seconda condizione dice che per ogni carattere della stringa X, l'automa cambia di stato in stato guidato dalla funzione T. L'ultima condizione dice che l'automa riconosce la stringa se l'ultimo carattere di X causa la transizione dell'automa in uno degli stati di accettazione, altrimenti la stringa non è riconosciuta.
L'insieme delle stringhe riconosciute dall'automa M forma un linguaggio formale chiamato linguaggio riconosciuto o linguaggio accettato dalla M. Il teorema di Kleene dimostra che la collezione dei linguaggi accettati da automi a stati finiti deterministici coincide con la collezione dei linguaggi regolari, cioè dei linguaggi forniti da espressioni regolari.
Le espressioni regolari sono chiamate anche espressioni razionali e di conseguenza i linguaggi che esse forniscono sono detti linguaggi razionali; questi termini sono giustificati dal fatto che questi oggetti si possono studiare con interessanti metodi algebrici, più precisamente mediante semigruppi finiti.
[modifica] Esempio
Il seguente esempio è una DFA M, con un alfabeto binario, che determina se l'input contiene un numero dispari di zeri.
M = (S, Σ, T, s, A) dove
- Σ = {0, 1},
- S = {S1, S2},
- s = S1,
- A = {S1}, and
- T è definita dalla seguente tabella di transizione di stato:
|
|
|
|
| S1 | S2 | S1 |
| S2 | S1 | S2 |
Il diagramma di stato per M è il seguente:
Semplicemente, lo stato S1 rappresenta lo stato in cui abbiamo sempre un numero dispari di zeri nell'input, mentre S2 indica un numero pari di zeri. Un 1 in input non cambia lo stato dell'automa. Quando l'input termina, lo stato mostrerà se l'input conteneva un numero dispari di zeri, o no.
Il linguaggio di M può essere descritto dal linguaggio regolare dato dalla seguente espressione regolare:
[modifica] Voci correlate
- Semiautoma
- Automa a stati finiti non deterministico
- Trasduttore di Mealy
- Automa a pila
- Macchina di Turing
[modifica] Bibliografia
- Noam Chomsky ....
- Rabin, Dana Scott ....
| Teoria degli automi: linguaggi formali e grammatiche formali | |||
|---|---|---|---|
| gerarchia di Chomsky |
Grammatiche | Linguaggi | automa minimo |
| Tipo-0 | (illimitato) | Ricorsivamente enumerabile | Macchina di Turing |
| (illimitato) | Ricorsivo | Decider | |
| Tipo-1 | Sensibile al contesto | Sensibile al contesto | Lineare-limitato |
| Tipo-2 | Libero dal contesto | Libero dal contesto | Automa a pila |
| Tipo-3 | Lineare (o Regolare) | Lineare (o Regolare) | A stati finiti |
| Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante. | |||
