Chomskyjeva hijerarhija

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži

U računarstvu, posebice 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[1] 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[uredi | uredi izvor]

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

Reference[uredi | uredi izvor]