• Konačni automat se koristi za prepoznavanje uzoraka.
• Stroj s konačnim automatom uzima niz simbola kao ulaz i u skladu s tim mijenja svoje stanje. U ulazu, kada se pronađe željeni simbol tada se događa prijelaz.
• Tijekom prijelaza, automati se mogu pomaknuti u sljedeće stanje ili ostati u istom stanju.
• FA ima dva stanja: stanje prihvaćanja ili stanje odbijanja. Kada je ulazni niz uspješno obrađen i automat dostigne svoje konačno stanje tada će prihvatiti.

Konačni automat sastoji se od sljedećeg:

P: konačan skup stanja
∑: konačan skup ulaznog simbola
q0: početno stanje
F: konačno stanje
d: Prijelazna funkcija

Prijelazna funkcija može se definirati kao

 δ: Q x ∑ →Q 

FA se karakterizira na dva načina:

1. DFA (konačni automati)
2. NDFA (nedeterministički konačni automati)

DFA

DFA je kratica za Deterministic Finite Automata. Deterministički se odnosi na jedinstvenost izračuna. U DFA, ulazni znak prelazi samo u jedno stanje. DFA ne prihvaća nulti potez što znači da DFA ne može promijeniti stanje bez ikakvog znaka unosa.

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

Primjer

Pogledajte primjer determinističkih konačnih automata:

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

NDFA

NDFA se odnosi na nedeterminističke konačne automate. Koristi se za prolazak kroz bilo koji broj stanja za određeni ulaz. NDFA prihvaća NULL potez što znači da može promijeniti stanje bez čitanja simbola.

NDFA također ima pet država isto kao i DFA. Ali NDFA ima drugačiju prijelaznu funkciju.

Prijelazna funkcija NDFA može se definirati kao:

Primjer

Pogledajte primjer nedeterminističkih konačnih automata:

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