Хиерархија на Чомски

Од Википедија — слободната енциклопедија
Прејди на: содржини, барај

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

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

Формални граматики[уреди]

Crystal Clear app xmag.svg Главна статија: „Формална граматика.

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

Формалната граматика го дефинира (или генерира) формалниот јазик, кој е (најверојатно бесконечно) множество на низи од симболи кои можат да бидат конструирани со примена на правилата врз низите од симболи кои на почетокот се состојат само од еден почетен симбол. Правило може да се примени на низа од симболи по пат на замена на секое појавување на симболите на левата страна од правилото со оние кои се појавуваат на десната страна. Низата на применети правила е наречена деривација. Вакваа граматика дефинира формален јазик на сите зборови кои може да се добијат со деривација од почетниот симбол.

Нетерминалните симболи вообичаено се претставуваат со големи букви, терминалните симболи со мали букви, а почетниот симбол со буквата S. Пример, граматиката со терминални симболи \{a, b\}, нетерминални симболи \{S, A, B\}, и правила:

S \rightarrow \, ABS
S \rightarrow \, ε (каде ε е празен стринг)
BA \rightarrow \, AB
BS \rightarrow \, b
Bb \rightarrow \, bb
Ab \rightarrow \, ab
Aa \rightarrow \, aa

и почетен симбол S, го дефинира јазикот на сите зборови во форма на  a^n b^n (т.е. n копија на a проследено со n копија на b). Во следниов пример е дадена поедноставна граматика која дефинира сличен јазик: Терминални симболи \{p, q\}, нетерминални симболи \{S\}, почетен симбол S, правила

S \rightarrow \, pSq
S \rightarrow \, ε

Хиерархија[уреди]

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

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

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

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

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

Граматика Јазици Автомат Правила
Тип-0 рекурзивно преброиви Тјурингова машина \alpha \rightarrow \beta (без ограничување)
Тип-1 контексно осетлива линеарно ограничена не детерминистичка Тјурингова машина \alpha A\beta \rightarrow \alpha\gamma\beta
Тип-2 контексно слободна Не детерминистички потисен автомат A \rightarrow \gamma
Тип-3 регуларна Конечен автомат A \rightarrow a and
A \rightarrow aB

Наводи[уреди]

  • Чомски, Ноам (1956). „Три модели за опис на јазикот“. „IRE Трансакции и Информациона Теорија“ (2): 113-124. 
  • Чомски, Ноам (1959). „On certain formal properties of grammars“. „Информација и Контрола“ (2): 137-167. 
  • Чомски, Ноам; Шуценбергер, Марсел П. (1963). „Алгебарската теорија на контексно слободни јазици“. Брафорт, П.; Хиршберг, Д.. „Компјутерско програмирање и Формални јазици“. Амстердам: North Holland. стр. 118-161. 

Надворешни врски[уреди]


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


Ноам Чомски
Библиографија (некомплетна)
Лингвистика: Синтаксни структури (1957) • Аспекти на теоријата на синтакса (1965) • The Sound Pattern of English (1968) • The Logical Structure of Linguistic Theory (1975) • Lectures on Government and Binding (1981) • The Minimalist Program (1995)
Политика: The Responsibility of Intellectuals (1967)American Power and the New MandarinsObjectivity and Liberal ScholarshipThe Fateful Triangle: The United States, Israel, and the Palestinians (1983) • Manufacturing Consent (with Edward Herman, 1988) • Necessary Illusions (1989) • Deterring Democracy (1992) • Class Warfare (1996) • Hegemony or Survival: America's Quest for Global Dominance (2003) • Failed States: The Abuse of Power and the Assault on Democracy (2006)
Филмографија
Manufacturing Consent: Noam Chomsky and the Media (1992) • Last Party 2000 (2001) • Power and Terror: Noam Chomsky in Our Times (2002) • Distorted Morality — America's War On Terror? (2003) • Noam Chomsky: Rebel Without a Pause (TV, 2003) • The Corporation (2003) • Peace, Propaganda & the Promised Land (2004)