• K rozpoznání vzorů se používá konečný automat.
• Stroj konečných automatů bere řetězec symbolů jako vstup a podle toho mění svůj stav. Když je na vstupu nalezen požadovaný symbol, dojde k přechodu.
• Během přechodu se automaty mohou buď přesunout do dalšího stavu, nebo zůstat ve stejném stavu.
• FA má dva stavy: stav přijetí nebo stav odmítnutí. Když je vstupní řetězec úspěšně zpracován a automaty dosáhnou konečného stavu, pak jej přijme.

Konečný automat se skládá z následujících částí:

Q: konečná množina stavů
∑: konečná množina vstupních symbolů
q0: počáteční stav
F: konečný stav
d: Přechodová funkce

Přechodovou funkci lze definovat jako

 δ: Q x ∑ →Q 

FA je charakterizován dvěma způsoby:

1. DFA (konečné automaty)
2. NDFA (nedeterministické konečné automaty)

DFA

DFA je zkratka pro Deterministic Finite Automata. Deterministický odkazuje na jedinečnost výpočtu. V DFA přejde vstupní znak pouze do jednoho stavu. DFA nepřijímá nulový přesun, což znamená, že DFA nemůže změnit stav bez jakéhokoli vstupního znaku.

DFA má pět n-tic {Q, ∑, q0, F, δ}

Příklad

Podívejte se na příklad deterministických konečných automatů:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 

NDFA

NDFA odkazují na nedeterministické konečné automaty. Používá se k přechodu libovolného počtu stavů pro konkrétní vstup. NDFA přijímá pohyb NULL, což znamená, že může změnit stav bez čtení symbolů.

NDFA má také pět států stejně jako DFA. Ale NDFA má jinou přechodovou funkci.

Přechodovou funkci NDFA lze definovat jako:

Příklad

Podívejte se na příklad nedeterministických konečných automatů:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3}