- 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:
- DFA (konačni automati)
- 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, δ}
P: skup svih stanja∑: konačan skup ulaznog simbola gdje je δ: Q x ∑ →Q
q0: početno stanje
F: konačno stanje
d: Prijelazna funkcija
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:
d: Q x ∑ →2QPrimjer
Pogledajte primjer nedeterminističkih konačnih automata:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 