- La macchina a stati finiti viene utilizzata per riconoscere i modelli.
- La macchina degli automi finiti prende la stringa del simbolo come input e cambia il suo stato di conseguenza. Nell'input, quando viene trovato il simbolo desiderato, avviene la transizione.
- Durante la transizione, gli automi possono passare allo stato successivo o rimanere nello stesso stato.
- La FA ha due stati: stato di accettazione o stato di rifiuto. Quando la stringa di input viene elaborata con successo e l'automa raggiunge il suo stato finale, accetterà.
Un automa finito è costituito da:
D: insieme finito di stati
∑: insieme finito di simboli di input
q0: stato iniziale
F: stato finale
d: funzione di transizione
La funzione di transizione può essere definita come
δ: Q x ∑ →Q
La FA si caratterizza in due modi:
- DFA (automi finiti)
- NDFA (automi finiti non deterministici)
DFAE
DFA sta per Automi Finiti Deterministici. Il determinismo si riferisce all'unicità del calcolo. In DFA, il carattere di input passa a un solo stato. DFA non accetta la mossa nulla, il che significa che il DFA non può cambiare stato senza alcun carattere di input.
DFA ha cinque tuple {Q, ∑, q0, F, δ}
D: insieme di tutti gli stati∑: insieme finito di simboli di input dove δ: Q x ∑ →Q
q0: stato iniziale
F: stato finale
d: funzione di transizione
Esempio
Vedi un esempio di automi finiti deterministici:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 
NDFA
Gli NDFA si riferiscono agli automi finiti non deterministici. Viene utilizzato per transitare in un numero qualsiasi di stati per un particolare input. NDFA accetta la mossa NULL, il che significa che può cambiare stato senza leggere i simboli.
L'NDFA ha anche cinque stati come il DFA. Ma l’NDFA ha una funzione di transizione diversa.
La funzione di transizione dell'NDFA può essere definita come:
d: Q x ∑ →2QEsempio
Vedi un esempio di automi finiti non deterministici:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 