• Konečný automat sa používa na rozpoznávanie vzorov.
• Stroj konečných automatov berie reťazec symbolov ako vstup a podľa toho mení svoj stav. Keď sa na vstupe nájde požadovaný symbol, dôjde k prechodu.
• Počas prechodu sa automaty môžu presunúť do ďalšieho stavu alebo zostať v rovnakom stave.
• FA má dva stavy: stav prijatia alebo stav odmietnutia. Keď je vstupný reťazec úspešne spracovaný a automaty dosiahnu konečný stav, potom budú akceptovať.

Konečný automat pozostáva z:

Q: konečná množina stavov
∑: konečná množina vstupných symbolov
q0: počiatočný stav
F: konečný stav
d: Prechodová funkcia

Prechodovú funkciu možno definovať ako

 δ: Q x ∑ →Q 

FA je charakterizovaná dvoma spôsobmi:

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

DFA

Skratka DFA znamená Deterministic Finite Automata. Deterministický odkazuje na jedinečnosť výpočtu. V DFA prechádza vstupný znak iba do jedného stavu. DFA neakceptuje nulový presun, čo znamená, že DFA nemôže zmeniť stav bez akéhokoľvek vstupného znaku.

DFA má päť n-tic {Q, ∑, q0, F, δ}

Príklad

Pozrite si príklad deterministických konečných automatov:

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

NDFA

NDFA odkazujú na nedeterministické konečné automaty. Používa sa na prechod ľubovoľného počtu stavov pre konkrétny vstup. NDFA akceptuje pohyb NULL, čo znamená, že môže zmeniť stav bez čítania symbolov.

NDFA má tiež päť štátov rovnakých ako DFA. Ale NDFA má inú prechodovú funkciu.

Prechodová funkcia NDFA môže byť definovaná ako:

Príklad

Pozrite si príklad nedeterministických konečných automatov:

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