• Baigtinės būsenos mašina naudojama modeliams atpažinti.
• Baigtinis automatas priima simbolio eilutę kaip įvestį ir atitinkamai keičia jos būseną. Įvestyje, kai randamas norimas simbolis, įvyksta perėjimas.
• Perėjimo metu automatai gali pereiti į kitą būseną arba likti toje pačioje būsenoje.
• FA turi dvi būsenas: priimti būseną arba atmesti būseną. Kai įvesties eilutė bus sėkmingai apdorota ir automatas pasieks galutinę būseną, jis priims.

Baigtinį automatą sudaro:

Klausimas: baigtinis būsenų rinkinys
∑: baigtinis įvesties simbolių rinkinys
q0: pradinė būsena
F: galutinė būsena
d: Perėjimo funkcija

Perėjimo funkciją galima apibrėžti kaip

 δ: Q x ∑ →Q 

FA apibūdinamas dviem būdais:

1. DFA (baigtiniai automatai)
2. NDFA (nedeterministiniai baigtiniai automatai)

DFA

DFA reiškia deterministinius baigtinius automatus. Deterministinis reiškia skaičiavimo unikalumą. DFA įvesties simbolis pereina tik į vieną būseną. DFA nepriima nulinio judėjimo, o tai reiškia, kad DFA negali pakeisti būsenos be jokio įvesties simbolio.

DFA turi penkias eilutes {Q, ∑, q0, F, δ}

Pavyzdys

Žr. deterministinių baigtinių automatų pavyzdį:

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

NDFA

NDFA reiškia nedeterministinius baigtinius automatus. Jis naudojamas perduoti bet kokį tam tikros įvesties būsenų skaičių. NDFA priima NULL judėjimą, o tai reiškia, kad jis gali pakeisti būseną neskaitydamas simbolių.

NDFA taip pat turi penkias būsenas, tokias pat kaip DFA. Tačiau NDFA turi skirtingą perėjimo funkciją.

NDFA pereinamąją funkciją galima apibrėžti taip:

Pavyzdys

Žr. nedeterministinių baigtinių automatų pavyzdį:

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