Chomskyjeva hijerarhija

U računarstvu, posebno u domeni programskih jezika, Chomskyjeva hijerarhija (rjeđe se koristi i termin Chomsky–Schützenbergerova hijerarhija) je hijerarhija klasa formalnih gramatika koje generiraju formalne jezike.

Hijerarhiju ovih gramatika (također zvanih i gramatike frazne strukture) je opisao Noam Chomsky 1956. godine"Computational Linguistics"  Također je imenovana po Marcel-Paulu Schützenbergeru koji je odigrao krucijalnu ulogu u razvoju teorije formalnih jezika.

Definicija: Jedna gramatika  se sastoji od 
Z = konačni broj znakova,
A = konačni broj znakova,
P = je konačni broj pravila,
S = znak iz Z, koji je startni zna.

 Tabela 

 Gramatika Pravila Automati Tip 0  Turing mašina Tip 1   linearna konačna nedeterministična Turing mašina (LKNM) Tip 2   nedeterministični podrumski automat Tip 3   Konačni automat

 Reference 

Kategorija:Formalni jezici