• Gli automi finiti vengono utilizzati per riconoscere modelli.
• Prende la stringa del simbolo come input e cambia il suo stato di conseguenza. Quando viene trovato il simbolo desiderato, avviene la transizione.
• Al momento della transizione gli automi possono passare allo stato successivo oppure restare nello stesso stato.
• Gli automi finiti hanno due stati, Accetta lo stato O Rifiuta lo stato . Quando la stringa di input viene elaborata con successo e l'automa raggiunge il suo stato finale, accetterà.

Definizione formale di FA

Un automa finito è una raccolta di 5 tuple (Q, ∑, δ, q0, F), dove:

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

Modello di automi finiti:

Gli automi finiti possono essere rappresentati dal nastro di input e dal controllo finito.

Nastro di ingresso: È un nastro lineare con un certo numero di celle. Ogni simbolo di input viene posizionato in ciascuna cella.

Controllo finito: Il controllo finito decide lo stato successivo alla ricezione di un input particolare dal nastro di input. Il lettore di nastri legge le celle una per una da sinistra a destra e alla volta viene letto solo un simbolo di input.

Tipi di automi:

Esistono due tipi di automi finiti:

1. DFA (automi finiti deterministici)
2. NFA (automi finiti non deterministici)

1. DFAE

DFA si riferisce ad automi finiti deterministici. Il determinismo si riferisce all'unicità del calcolo. Nel DFA, la macchina passa a uno stato solo per un particolare carattere di input. DFA non accetta la mossa nulla.

2. NFA

NFA sta per automi finiti non deterministici. Viene utilizzato per trasmettere un numero qualsiasi di stati per un particolare input. Può accettare la mossa nulla.

Alcuni punti importanti su DFA e NFA:

1. Ogni DFA è NFA, ma NFA non è DFA.
2. Possono esserci più stati finali sia in NFA che in DFA.
3. DFA viene utilizzato nell'analisi lessicale nel compilatore.
4. L'NFA è più un concetto teorico.