Konečnými automaty modelujeme chování jednoduchých objektů, které se mohou nacházet v různých stavech a přecházet mezi nimi na základě vstupu. Používá se při studiu vyčíslitelnosti a zpracování formálních jazyků. Známe konečné automaty deterministické a nedeterministické. Při konstrukci hardware se nejčastěji používají odvozené automaty typu Mealy a Moore.
Funkce konečného automatu by se dala definovat takto:
Deterministický konečný automat je charakteristický tím, že se vždy nachází právě v jednom ze svých vnitřních stavů.
Deterministický konečný automat je uspořádaná pětice € (Q, Q_0, F, X, \delta) €, kde € Q : |Q| < \infty € je konečná množina vnitřních stavů, € Q_0 : Q_0 \in Q € je počáteční stav, € F : F \subseteq Q € je množina koncových stavů, € X : |X| < \infty € je konečná vstupní abeceda (množina vstupních symbolů) a € \delta : Q \times X \to Q € je přechodová funkce.
Nedeterministický konečný automat je charakteristický tím, že se může v jednom okamžiku nacházet v celé množině svých vnitřních stavů (tedy více než v jednom). Nedeterministické konečné automaty lze převést na deterministické, avšak počet stavů se zvýší.
Nedeterministický konečný automat je uspořádaná pětice € (Q, Q_0, F, X, \delta) €, kde € Q : |Q| < \infty € je konečná množina vnitřních stavů, € Q_0 : Q_0 \subseteq Q \land Q_0 \neq \varnothing € je počáteční stav, € F : F \subseteq Q € je množina koncových stavů, € X : |X| < \infty € je konečná vstupní abeceda (množina vstupních symbolů) a € \delta : Q \times X \to \mathcal{P}(Q) € je přechodová funkce.
Poznámka: € \mathcal{P}(Q) € je potenční množina (množina všech podmnožin) Q.
Existuje i varianta s tzv. epsilon-přechody, kde epsilon znamená "prázdný vstup" a v praxi to znamená, že automat provádí přechody neustále, tedy nezávisle na čtení symbolů ze vstupu. Formální rozdíl je v definičním oboru přechodové funkce, jejíž signatura se změní na € \delta : Q \times (X \cup \epsilon) \to \mathcal{P}(Q) €.
Pokud se automat po přečtení celého vstupního řetězce nachází v jednom z konečných stavů, byl vstupní řetězec přijat. V ostatních případech přijat nebyl. Množina všech řetězců, které automat přijme, tvoří regulární jazyk nad jeho vstupní abecedou.
Konfigurace automatu se skládá z aktuálního stavu automatu a zbylé části vstupního řetězce, kterou automat dosud nepřečetl. Konfigurace nám umožňuje předvídat budoucí chování deterministického konečného automatu.