• Končni avtomat se uporablja za prepoznavanje vzorcev.
• Stroj s končnimi avtomati sprejme niz simbolov kot vhod in ustrezno spremeni svoje stanje. Ko je v vnosu najden želeni simbol, pride do prehoda.
• Med prehodom se lahko avtomati premaknejo v naslednje stanje ali ostanejo v istem stanju.
• FA ima dve stanji: stanje sprejema ali stanje zavrnitve. Ko je vhodni niz uspešno obdelan in avtomat doseže končno stanje, bo sprejel.

Končni avtomat je sestavljen iz naslednjega:

V: končna množica stanj
∑: končna množica vhodnih simbolov
q0: začetno stanje
F: končno stanje
d: Prehodna funkcija

Prehodno funkcijo lahko definiramo kot

 δ: Q x ∑ →Q 

FA je označen na dva načina:

1. DFA (končni avtomati)
2. NDFA (nedeterministični končni avtomati)

DFA

DFA je kratica za Deterministic Finite Automata. Deterministično se nanaša na edinstvenost izračuna. V DFA gre vhodni znak samo v eno stanje. DFA ne sprejema ničelne poteze, kar pomeni, da DFA ne more spremeniti stanja brez vnosnega znaka.

DFA ima pet tork {Q, ∑, q0, F, δ}

Primer

Oglejte si primer determinističnih končnih avtomatov:

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

NDFA

NDFA se nanaša na nedeterministične končne avtomate. Uporablja se za prehod poljubnega števila stanj za določen vhod. NDFA sprejme potezo NULL, kar pomeni, da lahko spremeni stanje brez branja simbolov.

NDFA ima tudi pet držav, enakih DFA. Toda NDFA ima drugačno prehodno funkcijo.

Prehodno funkcijo NDFA lahko definiramo kot:

Primer

Oglejte si primer nedeterminističnih končnih avtomatov:

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