- Na rozpoznávanie vzorov sa používajú konečné automaty.
- Ako vstup berie reťazec symbolov a podľa toho mení svoj stav. Keď sa nájde požadovaný symbol, dôjde k prechodu.
- V čase prechodu sa automaty môžu presunúť do ďalšieho stavu alebo zostať v tom istom stave.
- Konečné automaty majú dva stavy, Prijať stav alebo Odmietnuť štát . Keď je vstupný reťazec úspešne spracovaný a automaty dosiahnu konečný stav, potom budú akceptovať.
Formálna definícia FA
Konečný automat je súbor 5-tich (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 automatov:
Konečné automaty môžu byť reprezentované vstupnou páskou a konečným riadením.
Vstupná páska: Je to lineárna páska s určitým počtom buniek. Každý vstupný symbol je umiestnený v každej bunke.
Konečné ovládanie: Konečné riadenie rozhoduje o ďalšom stave po prijatí konkrétneho vstupu zo vstupnej pásky. Čítačka pásky číta bunky jednu po druhej zľava doprava a súčasne sa číta len jeden vstupný symbol.
Typy automatov:
Existujú dva typy konečných automatov:
- DFA (deterministické konečné automaty)
- NFA (nedeterministické konečné automaty)
1. DFA
DFA označuje deterministické konečné automaty. Deterministický odkazuje na jedinečnosť výpočtu. V DFA prejde stroj do jedného stavu len pre konkrétny vstupný znak. DFA neakceptuje nulový presun.
2. NFA
NFA znamená nedeterministické konečné automaty. Používa sa na prenos ľubovoľného počtu stavov pre konkrétny vstup. Môže prijať nulový ťah.
Niektoré dôležité body o službách DFA a NFA:
- Každé DFA je NFA, ale NFA nie je DFA.
- V NFA aj DFA môže existovať viacero konečných stavov.
- DFA sa používa v Lexikálnej analýze v kompilátore.
- NFA je skôr teoretický koncept.