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 Također je imenovana po Marcel-Paulu Schützenbergeru koji je odigrao krucijalnu ulogu u razvoju teorije formalnih jezika.

Definicija: Jedna gramatika $G$ se sastoji od $(Z,A,P,S)$ 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	$D\rightarrow E$ $D,E\in (Z\cup A)^{*},a\neq \epsilon$	Turing mašina
Tip 1	$D\rightarrow E$ $|D|\leq |E|,D,E\in (Z\cup A)^{*}$	linearna konačna nedeterministična Turing mašina (LKNM)
Tip 2	$D\rightarrow E$ $D\in Z,E\in (Z\cup A)^{*}$	nedeterministični podrumski automat
Tip 3	$D\rightarrow aE$ $D,E\in Z,a\in A$	Konačni automat