Automa finito deterministico
Finite Automaton può essere classificato in due tipi:
- Automa finito deterministico (DFA)
- Automa finito non deterministico (NDFA / NFA)
Automa finito deterministico (DFA)
In DFA, per ogni simbolo di input, è possibile determinare lo stato in cui si sposterà la macchina. Quindi, si chiamaDeterministic Automaton. Poiché ha un numero finito di stati, la macchina viene chiamataDeterministic Finite Machine o Deterministic Finite Automaton.
Definizione formale di un DFA
Un DFA può essere rappresentato da una tupla di 5 (Q, ∑, δ, q 0 , F) dove -
Q è un insieme finito di stati.
∑ è un insieme finito di simboli chiamato alfabeto.
δ è la funzione di transizione dove δ: Q × ∑ → Q
q0è lo stato iniziale da cui viene elaborato qualsiasi input (q 0 ∈ Q).
F è un insieme di stati finali di Q (F ⊆ Q).
Rappresentazione grafica di un DFA
Un DFA è rappresentato da digrafi chiamati state diagram.
- I vertici rappresentano gli stati.
- Gli archi etichettati con un alfabeto di input mostrano le transizioni.
- Lo stato iniziale è indicato da un singolo arco in entrata vuoto.
- Lo stato finale è indicato da doppi cerchi.
Esempio
Sia un automa finito deterministico →
- Q = {a, b, c},
- ∑ = {0, 1},
- q 0 = {a},
- F = {c} e
Funzione di transizione δ come mostrato dalla tabella seguente -
| Stato attuale | Stato successivo per ingresso 0 | Stato successivo per ingresso 1 |
|---|---|---|
| a | un | b |
| b | c | un |
| c | b | c |
La sua rappresentazione grafica sarebbe la seguente:
