Chomskyjeva hijerarhija

Izvor: Wikipedia

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[uredi - уреди]

Glavni članak: 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 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[uredi - уреди]

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.

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[uredi - уреди]

  • 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". u: Braffort, P.; Hirschberg, D.. Computer Programming and Formal Languages. Amsterdam: North Holland. str. 118-161. 
  • Siniša Srbljić (2003). Jezični procesori 1. Element. ISBN 953-197-129-3. 

Vanjske veze[uredi - уреди]

Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.