Teória automatov

Z Wikipédie

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


Formálne jazyky, automaty a gramatiky
Chomského
hierarchia
Gramatiky Jazyky Minimálny
automat
Typ-0 Frázová Rekurzívne vyčísliteľný Turingov stroj
Rekurzívny Vždy zastavujúci Turingov stroj
Typ-1 Kontextová Kontextová (Nedeterministický) lineárne ohraničený
Typ-2 Bezkontextová Bezkontextový (Nedeterministický) zásobníkový
Typ-3 Regulárna Regulárny Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.