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

Vista-xmag.png За више информација погледајте чланак 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“. In Braffort, P.; Hirschberg, D.. Computer Programming and Formal Languages. Amsterdam: North Holland. стр. 118-161. 

Spoljašnje veze[уреди]

Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.