Teória automatov

Teória automatov je časť informatiky zaoberajúca sa strojmi s konečným počtom stavov. Skúma ich matematickou reprezentáciou (automat, Turingov stroj).

Konečný automat je definovaný množinou stavov, počiatočným a konečným stavom, prechodovou funkciou a abecedou. Ku každému konečnému automatu existuje gramatika (vytvára slová). Gramatika je jednoznačne definovaná neterminálmi, terminálmi, pravidlami a počiatočným neterminálom. Automat sa dá zapísať tabuľkou, graficky alebo matematickou funkciou.
Príklad na gramatiku (napíše slovo abababab...)
 S→aB|ε (prázdna množina)
 B→bC|b
 C→aB

príklad na gramatiku (napíše nepárne číslo v binárnej sústave)
 S→1B|1
 B→0B|1B|1