Chomskyjeva hijerarhija

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

## Formalne gramatike

Formalnu gramatiku čine:
* konačan skup ''završnih znakova'';
* konačan skup ''nezavršnih znakova'';
* konačan skup *pravila produkcija* čije se lijeve i desne strane sastoje od slijeda takvih znakova
* istaknuti *početni nezavršni znak*.

Formalna gramatika definira (ili *generira*) *formalni jezik*, koji je (moguće beskonačan) skup nizova znakova koji se mogu izgraditi primjenom produkcijskih pravila nad slijedom znakova koji inicijalno sadrži samo istaknuti početni nezavršni znak. Pravilo može biti primjenjeno na međuniz znakova jednostavnom zamjenom pojavljivanja znaka na lijevoj strani produkcije znakovima koji se pojavljuju na desnoj strani. Slijed primjene pravila zovemo *produkcija* (rijetko i *derivacija*). Takva gramatika definira formalni jezik čije se riječi sastoje od završnih znakova koji se mogu dohvatiti primjenom produkcija na početni nezavršni znak.

Nezavršni se znakovi obično pišu velikim slovima, završni malim slovima, dok početni nezavršni znak označavamo specijalnim znakom S. Na primjer, gramatika sa završnim znakovima \{a, b\}, nezavršnim znakovima \{S, A, B\}, produkcijama
: S \rightarrow \, ABS
: S \rightarrow \, ε (pri čemu je ε prazni niz)
: BA \rightarrow \, AB
: BS \rightarrow \, b
: Bb \rightarrow \, bb
: Ab \rightarrow \, ab
: Aa \rightarrow \, aa
i početnim nezavršnim znakom S, definira jezik svih riječi oblika  a^n b^n  (tj. n kopija znaka a nakon kojih slijedi n kopija znaka b).
Slijedi jednostavna gramatika koja definira sličan jezik:
Završni znakovi su \{p, q\}, nezavršni znakovi su \{S\}, početni nezavršni znak je S, a produkcije:
: S \rightarrow \, pSq
: S \rightarrow \, ε

## Hijerarhija
Chomskyjeva se hijerarhija sastoji od sljedećih razina:
* Gramatike tipa 0 (gramatike neograničenih 
produkcija) uključuju sve formalne gramatike. Generiraju točno sve jezike koje može prepoznati Turingov stroj. Ovi su jezici još i poznati kao rekurzivno prebrojivi jezici. Uočimo razliku između njih i rekurzivnih jezika koje *odlučuje* Turingov stroj koji uvijek staje.
* Gramatike tipa 1 (kontekstno ovisne gramatike) generiraju kontekstno ovisne jezike. Ove gramatike imaju produkcije oblika \alpha A\beta \rightarrow \alpha\gamma\beta pri čemu je A nezavršni znak te \alpha, \beta i \gamma nizovi završnih i nezavršnih znakova. Nizovi znakova \alpha i \beta mogu biti prazni, ali niz znakova \gamma mora biti neprazan. Produkcija S \rightarrow \epsilon je dozvoljena ako se S ne pojavljuje na desnoj strani neke produkcije. Jezici koje gramatike ovog tipa opisuju su točno svi jezici koje može prepoznati linearno ograničen automat (nedeterministički Turingov stroj čija je traka ograničena konstantom puta duljina ulaza.)
* Gramatike tipa 2 (kontekstno neovisne gramatike) generiraju kontekstno neovisne jezike. Imaju produkcije oblika A \rightarrow \gamma pri čemu je A nezavršni znak i \gamma niz završnih i nezavršnih znakova. Ovi jezici su točno svi oni jezici koje može prepoznati nedeterministički potisni automat. Kontekstno neovisni jezici su teoretska baza za sintaksu većine programskih jezika.
* Gramatika tipa 3 (regularne gramatike) generiraju regularne jezike. Takva gramatika ograničava svoje produkcije na jedan nezavršni znak na lijevoj strani produkcije pri čemu se desna strana može sastojati samo od jednog završnog znaka, nakon kojeg slijedi (ili prethodi, ali ne i oboje u istoj gramatici) jedan nezavršni znak. Produkcija S \rightarrow \epsilon je ovdje također dozvoljena ukoliko se S ne pojavljuje na desnoj strani neke od produkcija. Ovi jezici su točno svi oni jezici koje može odlučiti konačni automat. Dodatno, ova familija formalnih jezika može biti opisana regularnim izrazima. Regularni jezici se obično koriste za definiranje uzoraka pretrage te analizu leksičke strukture programskog jezika.

Uočimo da skup gramatika koji odgovara rekurzivnim jezicima nije prisutan u ovoj hijerarhiji.

Svaki regularni jezik je kontekstno neovisan, svaki kontekstno neovisni jezik je kontekstno ovisan, svaki kontekstno ovisni jezik je rekurzivan i svaki rekurzivni jezik je rekurzivno prebrojiv. Ovo su sve pravi podskupovi (inkluzije), što znači da postoje nerekurzivni rekurzivno prebrojivi jezici, rekurzivni jezici koji nisu kontekstno ovisni, kontekstno ovisni jezici koji nisu kontekstno neovisni kao i neregularni kontekstno neovisni jezici.

Sljedeća tablica predstavlja sažetak tipova gramatika u Chomskyjevoj hijerarhiji, klase jezika koje generiraju, tip automata koji ih prepoznaje, te oblik produkcija koje moraju imati.

## Izvori
* 
* 
* 
* 

## Vanjske veze
* http://www.staff.ncl.ac.uk/hermann.moisl/ell236/lecture5.htm