Chomskyjeva hijerarhija
Izgled
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[1] 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
[uredi | uredi izvor]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 |