- K rozpoznání vzorů se používají konečné automaty.
- Vezme řetězec symbolů jako vstup a podle toho změní jeho stav. Když je nalezen požadovaný symbol, dojde k přechodu.
- V době přechodu se mohou automaty buď přesunout do dalšího stavu, nebo ve stejném stavu zůstat.
- Konečné automaty mají dva stavy, Přijmout stav nebo Odmítnout stát . Když je vstupní řetězec úspěšně zpracován a automaty dosáhnou konečného stavu, přijme je.
Formální definice FA
Konečný automat je soubor 5-ti n-tic (Q, ∑, δ, q0, F), kde:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Model konečných automatů:
Konečné automaty mohou být reprezentovány vstupní páskou a konečným řízením.
Vstupní páska: Je to lineární páska s určitým počtem buněk. Každý vstupní symbol je umístěn v každé buňce.
Konečné ovládání: Konečné řízení rozhoduje o dalším stavu při příjmu konkrétního vstupu ze vstupní pásky. Čtečka pásky čte buňky jednu po druhé zleva doprava a současně se čte pouze jeden vstupní symbol.
Typy automatů:
Existují dva typy konečných automatů:
- DFA (deterministické konečné automaty)
- NFA (nedeterministické konečné automaty)
1. DFA
DFA označuje deterministické konečné automaty. Deterministický odkazuje na jedinečnost výpočtu. V DFA přejde stroj do jednoho stavu pouze pro určitý vstupní znak. DFA nepřijímá nulový přesun.
2. NFA
NFA je zkratka pro nedeterministické konečné automaty. Používá se k přenosu libovolného počtu stavů pro konkrétní vstup. Může přijmout nulový tah.
Některé důležité body o DFA a NFA:
- Každé DFA je NFA, ale NFA není DFA.
- V NFA i DFA může existovat více konečných stavů.
- DFA se používá v Lexikální analýze v kompilátoru.
- NFA je spíše teoretický koncept.