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

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

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

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

За више информација погледајте чланак Формална граматика

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

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

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

Незавршни знакови се обично пишу великим словима, завршни малим словима, док почетни незавршни знак означавамо специјалним знаком $С$. На пример, граматика са завршним знаковима $\{а, б\}$, незавршним знаковима $\{С, А, Б\}$, правилима извођења

$С$$\ригхтарроw \,$$АБС$

$С$$\ригхтарроw \,$ε (при чему је ε празни низ)

$БА$$\ригхтарроw \,$$АБ$

$БС$$\ригхтарроw \,$$б$

$Бб$$\ригхтарроw \,$$бб$

$Аб$$\ригхтарроw \,$$аб$

$Аа$$\ригхтарроw \,$$аа$

и почетним незавршним знаком $С$, дефинише језик свих речи облика $а^н б^н$ (тј. $н$ копија знака $а$ након којих следи $н$ копија знака $б$). Следи једноставна граматика која дефинише сличан језик: Завршни знакови су $\{п, q\}$, незавршни знакови су $\{С\}$, почетни незавршни знак је $С$, а правила извођења:

$С$$\ригхтарроw \,$$пСq$

$С$$\ригхтарроw \,$ε

Хијерархија

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

• Граматике типа 0 (граматике без ограничења) укључују све формалне граматике. Генеришу све језике које може препознати Тјурингова машина. Ови језици су још и познати као рекурзивно пребројиви језици. Уочимо разлику између њих и рекурзивних језика које одлучује Тјурингова машина која увек стаје.
• Граматике типа 1 (контекстно осетљиве граматике) генеришу контекстно осетљиве језике. Ове граматике имају правила извођења облика $\алпха А\бета \ригхтарроw \алпха\гамма\бета$при чему је $А$незавршни знак, а $\алпха$, $\бета$и $\гамма$низови завршних и незавршних знакова. Низови знакова $\алпха$и $\бета$могу бити празни, али низ знакова $\гамма$мора бити непразан. Извођење $С \ригхтарроw \епсилон$је дозвољено ако се $С$не појављује на десној страни неке продукције. Језици које граматике овог типа описују су тачно сви језици које може препознати линеарно ограничен аутомат (недетерминистичка Тјурингова машина чија је трака ограничена константом пута дужина улаза.)
• Граматике типа 2 (контекстно слободне граматике) генеришу контекстно слободне језике. Имају правила извођења облика $А \ригхтарроw \гамма$при чему је $А$незавршни знак и $\гамма$низ завршних и незавршних знакова. Ови језици су тачно сви они језици које може препознати недетерминистички потисни аутомат. Контекстно слободни језици су теоријска база за синтаксу већине програмских језика.
• Граматика типа 3 (регуларне граматике) генеришу регуларне језике. Таква граматика је ограничена на правила извођења са једним незавршним знаком на левој страни правила, док се десна страна може састојати само од једног завршног знака, након којег евентуално следи (или претходи, али не и обоје у истој граматици) један незавршни знак. Продукција $С \ригхтарроw \епсилон$је такође дозвољена уколико се $С$не појављује на десној страни неке од продукција. Ови језици су тачно сви језици које може одлучити коначни аутомат. Додатно, ова фамилија формалних језика може бити описана регуларним изразима. Регуларни језици се обично користе за дефинисање узорака претраге и лексичку анализу програмских језика.

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

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

Следећа табела представља типове граматика у хијерархији Чомског, класе језика које генеришу, тип аутомата који их препознаје и облик правила извођења које морају имати.

Граматика	Језици	Аутомат	Правила извођења
Тип 0	Рекурзивно пребројиви	Тјурингова машина	$\алпха \ригхтарроw \бета$(без ограничења)
Тип 1	Контекстно осетљива	Линеарно ограничена недетерминистичка Тјурингова машина	$\алпха А\бета \ригхтарроw \алпха\гамма\бета$
Тип 2	Контекстно слободна	Недетерминистички потисни аутомат	$А \ригхтарроw \гамма$
Тип 3	Регуларна	Коначни аутомат	$А \ригхтарроw \епсилон$и $А \ригхтарроw аБ$

Референце

• 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. 

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

• http://www.chomsky.info/
• http://www.staff.ncl.ac.uk/hermann.moisl/ell236/lecture5.htm