Hijerarhija Čomskog

U računarstvu, posebno u oblasti programskih jezika, hijerarhija Čomskog (ponekad se koristi i termin hijerarhija Čomski–Šutcenbergera) je hijerarhija klasa formalnih gramatika.

Hijerarhiju ovih gramatika je opisao Noam Čomski 1956. (vidi  [1]). Takođe je imenovana po Marsel-Paulu Šutcenbergeru koji je odigrao ključnu ulogu u razvoju teorije formalnih jezika.

Formalne gramatike

Glavni članak: Formalna gramatika

Formalnu gramatiku čine:

• konačan skup završnih znakova;
• konačan skup nezavršnih znakova;
• konačan skup pravila izvođenja čije se leve i desne strane sastoje od nizova takvih znakova
• početni nezavršni znak.

Formalna gramatika definiše (ili generiše) formalni jezik, koji je (moguće beskonačan) skup nizova znakova koji se mogu izgraditi primenom pravila izvođenja nad nizom znakova koji inicijalno sadrži samo početni nezavršni znak. Pravilo može biti primenjeno na međuniz znakova jednostavnom zamenom pojavljivanja znaka na levoj strani produkcije znakovima koji se pojavljuju na desnoj strani. Redosled primene pravila zovemo izvođenje (ponekad i derivacija). Takva gramatika definiše formalni jezik čije se reči sastoje isključivo od završnih znakova koji se mogu dobiti primenom izvođenja na početni nezavršni znak.

Nezavršni znakovi se obično pišu velikim slovima, završni malim slovima, dok početni nezavršni znak označavamo specijalnim znakom $S$. Na primer, gramatika sa završnim znakovima $\{a,b\}$, nezavršnim znakovima $\{S,A,B\}$, pravilima izvođenja

$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$, definiše jezik svih reči oblika $a^{n}b^{n}$ (tj. $n$ kopija znaka $a$ nakon kojih sledi $n$ kopija znaka $b$). Sledi jednostavna gramatika koja definiše sličan jezik: Završni znakovi su $\{p,q\}$, nezavršni znakovi su $\{S\}$, početni nezavršni znak je $S$, a pravila izvođenja:

$S$ $\rightarrow \,$ $pSq$

$S$ $\rightarrow \,$ ε

Hijerarhija

Hijerarhija Čomskog se može podeliti na sledeće tipove:

• Gramatike tipa 0 (gramatike bez ograničenja) uključuju sve formalne gramatike. Generišu sve jezike koje može prepoznati Tjuringova mašina. Ovi jezici su još i poznati kao rekurzivno prebrojivi jezici. Uočimo razliku između njih i rekurzivnih jezika koje odlučuje Tjuringova mašina koja uvek staje.
• Gramatike tipa 1 (kontekstno osetljive gramatike) generišu kontekstno osetljive jezike. Ove gramatike imaju pravila izvođenja oblika $\alpha A\beta \rightarrow \alpha \gamma \beta$ pri čemu je $A$ nezavršni znak, a $\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. Izvođenje $S\rightarrow \epsilon$ je dozvoljeno ako se $S$ ne pojavljuje na desnoj strani neke produkcije. Jezici koje gramatike ovog tipa opisuju su tačno svi jezici koje može prepoznati linearno ograničen automat (nedeterministička Tjuringova mašina čija je traka ograničena konstantom puta dužina ulaza.)
• Gramatike tipa 2 (kontekstno slobodne gramatike) generišu kontekstno slobodne jezike. Imaju pravila izvođenja oblika $A\rightarrow \gamma$ pri čemu je $A$ nezavršni znak i $\gamma$ niz završnih i nezavršnih znakova. Ovi jezici su tačno svi oni jezici koje može prepoznati nedeterministički potisni automat. Kontekstno slobodni jezici su teorijska baza za sintaksu većine programskih jezika.
• Gramatika tipa 3 (regularne gramatike) generišu regularne jezike. Takva gramatika je ograničena na pravila izvođenja sa jednim nezavršnim znakom na levoj strani pravila, dok se desna strana može sastojati samo od jednog završnog znaka, nakon kojeg eventualno sledi (ili prethodi, ali ne i oboje u istoj gramatici) jedan nezavršni znak. Produkcija $S\rightarrow \epsilon$ je takođe dozvoljena ukoliko se $S$ ne pojavljuje na desnoj strani neke od produkcija. Ovi jezici su tačno svi 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 definisanje uzoraka pretrage i leksičku analizu programskih jezika.

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

Svaki regularni jezik je kontekstno slobodan, svaki kontekstno slobodni jezik je kontekstno osetljiv, svaki kontekstno osetljiv 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 osetljivi, kontekstno osetljivi jezici koji nisu kontekstno slobodni kao i neregularni kontekstno slobodni jezici.

Sledeća tabela predstavlja tipove gramatika u hijerarhiji Čomskog, klase jezika koje generišu, tip automata koji ih prepoznaje i oblik pravila izvođenja koje moraju imati.

Gramatika	Jezici	Automat	Pravila izvođenja
Tip 0	Rekurzivno prebrojivi	Tjuringova mašina	$\alpha \rightarrow \beta$ (bez ograničenja)
Tip 1	Kontekstno osetljiva	Linearno ograničena nedeterministička Tjuringova mašina	$\alpha A\beta \rightarrow \alpha \gamma \beta$
Tip 2	Kontekstno slobodna	Nedeterministički potisni automat	$A\rightarrow \gamma$
Tip 3	Regularna	Konačni automat	$A\rightarrow \epsilon$ i $A\rightarrow aB$

Reference

• 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. Computer Programming and Formal Languages. Amsterdam: North Holland. стр. 118—161. CS1 одржавање: Вишеструка имена: списак уредника (веза)

Spoljašnje veze

• https://web.archive.org/web/20180913103525/https://chomsky.info/
• http://www.staff.ncl.ac.uk/hermann.moisl/ell236/lecture5.htm