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

Formalne gramatike

Podrobniji članak o temi: Formalna gramatika

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 primijenjeno 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 ako 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.

Gramatika	Jezici	Automat	Pravila produkcija
Tip 0	Rekurzivno prebrojivi	Turingov stroj	$\alpha \rightarrow \beta$ (bez ograničenja)
Tip 1	Kontekstno ovisna	Linearno ograničeni nedeterministički Turingov stroj	$\alpha A\beta \rightarrow \alpha \gamma \beta$
Tip 2	Kontekstno neovisna	Nedeterministički potisni automat	$A\rightarrow \gamma$
Tip 3	Regularna	Konačni automat	$A\rightarrow \epsilon$ i $A\rightarrow aB$

Izvori

• Chomsky, Noam. 1956. Three models for the description of language. IRE Transactions on Information Theory (2): 113–124
• Chomsky, Noam. 1959. On certain formal properties of grammars. Information and Control (2): 137–167
• Chomsky, Noam; Schützenberger, Marcel P. 1963. The algebraic theory of context free languages. Braffort, P.; Hirschberg, D. (ur.). Computer Programming and Formal Languages. North Holland. Amsterdam. str. 118–161CS1 održavanje: više imena: editors list (link)
• Siniša Srbljić. 2003. Jezični procesori 1. Element. ISBN 953-197-129-3

Vanjske poveznice

• http://www.staff.ncl.ac.uk/hermann.moisl/ell236/lecture5.htm