- 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:
- DFA (končni avtomati)
- 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, δ}
V: množica vseh stanj∑: končna množica vhodnih simbolov, kjer je δ: Q x ∑ →Q
q0: začetno stanje
F: končno stanje
d: Prehodna funkcija
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:
d: Q x ∑ →2QPrimer
Oglejte si primer nedeterminističnih končnih avtomatov:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 