Преглед на кодот на Хиерархија на Чомски

Во [[компјутерски науки|компјутерските науки]], особено во делот на [[програмски јазици]], '''Хиерархијата на Чомски''' (честопати нарекувана и како '''Чомски-Шуценбергеровара хиерархија''' е хиерархиска класа на [[формална граматика|формални граматики]] кои генерираат [[формален јазик|формални јазици]].

Оваа хиерархија на граматики била опишана од страна на американскиот јазичар [[Ноам Чомски]] во 1956 година.  Оваа хиерархија исто така е именувана и по [[Марцел-Пол Шуценбергер]] кој имал главна улога во развојот на теоријата на [[формален јазик|формални јазици]].

== Формални граматики ==
{{Главна|Формална граматика}}

Формалната граматика се состои од :

* конечно множество на [[Терминален симбол|''терминални симболи'']];
* конечно множество на ''[[нетерминални симболи]]'';
* конечно множество на ''правила'' со лева- и десна- страна кои се состојат од низа на овие симболи 
* ''почетен симбол''.

Формалната граматика го дефинира (или ''генерира'') ''формалниот јазик'', кој е (најверојатно бесконечно) множество на низи од симболи кои можат да бидат конструирани со примена на правилата врз низите од симболи кои на почетокот се состојат само од еден почетен симбол. Правило може да се примени на низа од симболи по пат на замена на секое појавување на симболите на левата страна од правилото со оние кои се појавуваат на десната страна. Низата на применети правила е наречена ''деривација''. Вакваа граматика дефинира формален јазик на сите зборови кои може да се добијат со деривација од почетниот симбол. 
 
Нетерминалните симболи вообичаено се претставуваат со големи букви, терминалните симболи со мали букви, а почетниот симбол со буквата <math>S</math>. Пример, граматиката со терминални симболи <math>\{a, b\}</math>, нетерминални симболи <math>\{S, A, B\}</math>, и правила:
: <math>S</math> <math>\rightarrow \,</math> <math>ABS</math>
: <math>S</math> <math>\rightarrow \,</math> ε  (каде ε е празен стринг)
: <math>BA</math> <math>\rightarrow \,</math> <math>AB</math>
: <math>BS</math> <math>\rightarrow \,</math> <math>b</math>
: <math>Bb</math> <math>\rightarrow \,</math> <math>bb</math>
: <math>Ab</math> <math>\rightarrow \,</math> <math>ab</math>
: <math>Aa</math> <math>\rightarrow \,</math> <math>aa</math>
и почетен симбол <math>S</math>, го дефинира јазикот на сите зборови во форма на <math> a^n b^n </math> (т.е. <math>n</math> копија на <math>a</math> проследено со <math>n</math> копија на <math>b</math>).
Во следниов пример е дадена поедноставна граматика која дефинира сличен јазик: 
Терминални симболи <math>\{p, q\}</math>, нетерминални симболи <math>\{S\}</math>, почетен симбол <math>S</math>, правила
: <math>S</math> <math>\rightarrow \,</math> <math>pSq</math>
: <math>S</math> <math>\rightarrow \,</math> ε

== Хиерархија ==
Хиерархијата на Чомски се состои од следниве нивоа:

* Тип-0 граматики ([[неограничена граматика|неограничени граматики]]) ги вклучуваат сите формални граматики. Тие ги генерираат сите јазици кои можат да бидат препознаени од [[Тјурингова машина|Тјуринговата машина]]. Овие јазици исто така се познати и како [[рекурзивно преброив јазик|рекурзивно преброиви јазици]]. Да напоменеме дека овие јазици се различни од [[рекурзивен јазик|рекурзивните јазици]] кои можат да бидат ''одлучени'' од страна на [[машини кои секогаш завршуваат|Тјуринговите машини кои секогаш завршуваат]]
* Тип-1 граматики ([[контексно осетлива граматика|контексно осетливи граматики]]) генерираат [[контексно осетлив јазик|контексно осетливи јазици]]. Овие граматики имаат правила во следнава форма <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math> со <math>A</math> нетерминален симбол и <math>\alpha</math>, <math>\beta</math> и <math>\gamma</math> стрингови на терминални и нетерминални симболи. Стринговите <math>\alpha</math> и <math>\beta</math> може да бидат празни, но стрингот <math>\gamma</math> не смее да биде празен. Правилото <math>S \rightarrow \epsilon</math> е допуштено ако <math>S</math> не се појавува на десната страна од било кое правило. Јазиците опишани со овие граматики се точно оние јазици кои можат да бидат препознаени од страна на [[линеарно ограничен автомат]] (неограничена Тјурингова машина чија лента е ограничена на константен број од должината на влезот).
* Тип-2 граматики ([[контексно слободна граматика|контексно слободни граматики]]) генерираат [[контексно слободен јазик|контексно слободни јазици]]. Овие граматики се дефинирани со правила во форма <math>A \rightarrow \gamma</math> со <math>A</math> како нетерминален симбол и <math>\gamma</math> како стринг на терминали и нетерминали. Тоа се оние јазици кои можат да бидат препознаени од неограничени [[потисен автомат|потисни автомати]]. Контексно слободните јазици теоретски се основа на синтаксата на повеќето [[програмски јазик|програмски јазици]].
* Тип-3 граматики ([[регуларна граматика|регуларни граматики]]) генерираат [[регуларен јазик|регуларни јазици]]. Овие граматики ги ограничуваат своите правила на еден нетерминален симбол на левата страна и еден терминален симбол на десната страна, со можност да му следи  (или претходи, но не и двете одеднаш во иста граматика) еден нетерминален симбол. Правилото <math>S \rightarrow \epsilon</math> тука е допуштено ако <math>S</math> не се појавува на десната страна од било кое правило. Тоа се оние јазици кои можат да бидат одлучени од страна на [[конечен автомат|конечни автомати]]. Уште повеќе, оваа фамилија на формални јазици може да биде добиена и со [[регуларни изрази]]. Регуларните јазици вообичаено се користат за дефинирање на стрингови за пребарување во лексичката структура на програмските јазици.

Да напоменеме дека множеството од граматики кои соодветствуваат на рекурзивните јазици не е член на оваа хиерархија.

Секој регуларен јазик е контексно слободен, секој контексно слободен јазик е контексно осетлив и секој контексно осетлив јазик е рекурзивен а секој рекурзивен јазик е рекурзивно преброив. Ова се вистински подмножества, што значи дека постојат рекурзивно преброиви јазици кои не се рекурзивни, рекурзивни јазици кои не се контексно осетливи, контексно осетливи јазици кои не се контексно слободни и контексно слободни јазици кои се не регуларни.

Следната табела е сумарен приказ на секој од четирите типа на граматики на Чомски, класата на јазик кој го генерира, типот на автомат кој го препознава, и формата на неговите правила.

{| class="wikitable"
|-
! Граматика
! Јазици
! Автомат
! Правила
|-
| Тип-0
| [[рекурзивно преброив јазик|рекурзивно преброиви]]
| [[Тјурингова машина]]
| <math>\alpha \rightarrow \beta</math> (без ограничување)
|-
| Тип-1
| [[контексно осетлива граматика|контексно осетлива]]
| [[линеарно ограничен автомат|линеарно ограничена не детерминистичка Тјурингова машина]]
| <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math>
|-
| Тип-2
| [[контексно слободна граматика|контексно слободна]]
| Не детерминистички [[потисен автомат]]
| <math>A \rightarrow \gamma</math>
|-
| Тип-3
| [[регуларна граматика|регуларна]]
| [[Конечен автомат]]
| <math>A \rightarrow a</math> and<br /><math>A \rightarrow aB</math>
|}

== Наводи ==
* {{наведено списание
 | last = Чомски
 | first = Ноам
 | year = 1956
 | title = Три модели за опис на јазикот
 | journal = IRE Трансакции и Информациона Теорија
 | issue = 2
 | pages = 113-124
 }}
* {{наведено списание
 | last = Чомски
 | first = Ноам
 | year = 1959
 | title = On certain formal properties of grammars
 | journal = Информација и Контрола 
 | issue = 2
 | pages = 137-167
 }}
* {{наведена книга
 | last = Чомски
 | first = Ноам
 |author2=Шуценбергер, Марсел П.
 | editor = Брафорт, П.; Хиршберг, Д.
 | others = 
 | title =  Компјутерско програмирање и Формални јазици
 | year = 1963
 | month = 
 | publisher = North Holland
 | location = Амстердам
 | id = 
 | pages = 118-161
 | chapter = Алгебарската теорија на контексно слободни јазици
 }}

== Надворешни врски ==
* http://www.staff.ncl.ac.uk/hermann.moisl/ell236/lecture5.htm

{{формални јазици и граматики}}

{{Ноам Чомски}}

[[Категорија:Формални јазици]]
[[Категорија:Генеративни јазичарики]]
[[Категорија:Ноам Чомски]]