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

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

Хијерархију ових граматика је описао Ноам Чомски 1956. (види  [1]). Такође је именована по Марсел-Паулу Шутценбергеру који је одиграо кључну улогу у развоју теорије формалних језика.

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

Главни чланак: Формална граматика

Формалну граматику чине:

• коначан скуп завршних знакова;
• коначан скуп незавршних знакова;
• коначан скуп правила извођења чије се леве и десне стране састоје од низова таквих знакова
• почетни незавршни знак.

Формална граматика дефинише (или генерише) формални језик, који је (могуће бесконачан) скуп низова знакова који се могу изградити применом правила извођења над низом знакова који иницијално садржи само почетни незавршни знак. Правило може бити примењено на међуниз знакова једноставном заменом појављивања знака на левој страни продукције знаковима који се појављују на десној страни. Редослед примене правила зовемо извођење (понекад и деривација). Таква граматика дефинише формални језик чије се речи састоје искључиво од завршних знакова који се могу добити применом извођења на почетни незавршни знак.

Незавршни знакови се обично пишу великим словима, завршни малим словима, док почетни незавршни знак означавамо специјалним знаком $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 \epsilon$ и $A\rightarrow aB$

Референце

• Цхомскy, Ноам (1956). „Тхрее моделс фор тхе десцриптион оф лангуаге”. ИРЕ Трансацтионс он Информатион Тхеорy (2): 113—124. 
• Цхомскy, Ноам (1959). „Он цертаин формал пропертиес оф граммарс”. Информатион анд Цонтрол (2): 137—167. 
• Цхомскy, Ноам; Сцхüтзенбергер, Марцел П. (1963). „Тхе алгебраиц тхеорy оф цонтеxт фрее лангуагес”. Ур.: Браффорт, П.; Хирсцхберг, D. Цомпутер Программинг анд Формал Лангуагес. Амстердам: Нортх Холланд. стр. 118—161. ЦС1 одржавање: Вишеструка имена: списак уредника (веза)

Спољашње везе

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