- Končni avtomati se uporabljajo za prepoznavanje vzorcev.
- Kot vhod vzame niz simbolov in ustrezno spremeni svoje stanje. Ko je želeni simbol najden, pride do prehoda.
- V času prehoda se lahko avtomati premaknejo v naslednje stanje ali ostanejo v istem stanju.
- Končni avtomati imajo dve stanji, Sprejmi stanje oz Zavrni stanje . Ko je vhodni niz uspešno obdelan in avtomat doseže končno stanje, bo sprejel.
Formalna definicija FA
Končni avtomat je zbirka 5-tuple (Q, ∑, δ, q0, F), kjer:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Model končnega avtomata:
Končne avtomate lahko predstavimo z vhodnim trakom in končnim krmiljenjem.
Vhodni trak: To je linearni trak z določenim številom celic. Vsak vhodni simbol je postavljen v vsako celico.
Končni nadzor: Končni nadzor odloči o naslednjem stanju ob prejemu določenega vnosa z vhodnega traku. Čitalnik traku bere celice eno za drugo od leve proti desni in naenkrat bere samo en vhodni simbol.
Vrste avtomatov:
Obstajata dve vrsti končnih avtomatov:
- DFA (deterministični končni avtomati)
- NFA (nedeterministični končni avtomati)
1. DFA
DFA se nanaša na deterministične končne avtomate. Deterministično se nanaša na edinstvenost izračuna. V DFA stroj preide v eno stanje samo za določen vhodni znak. DFA ne sprejme ničelne poteze.
2. NFA
NFA pomeni nedeterministične končne avtomate. Uporablja se za prenos poljubnega števila stanj za določen vhod. Lahko sprejme ničelno potezo.
Nekaj pomembnih točk o DFA in NFA:
- Vsak DFA je NFA, vendar NFA ni DFA.
- V NFA in DFA je lahko več končnih stanj.
- DFA se uporablja v leksikalni analizi v prevajalniku.
- NFA je bolj teoretični koncept.