Иерархия Хомского: различия между версиями

Версия от 11:23, 23 октября 2009

Иерархия Хомского (Chomsky hierarchy) - четыре типа грамматик и языков: праволинейные, контекстно-свободные,контекстно-зависимые, составляющих.

Заметим, что согласно определению каждая праволинейная грамматика контекстно-свободная, но контекстно-свободная грамматика, содержащая [math]\displaystyle{ e }[/math]-правила, не является контекстно-зависимой.

Запрещение [math]\displaystyle{ e }[/math]-правил в контекстно-зависимой грамматике вызвано желанием гарантировать так называемую рекурсивность порождаемого ею языка. Иначе говоря, желанием иметь алгоритм, который для произвольной контекстно-зависимой грамматики [math]\displaystyle{ G }[/math] и входной цепочки [math]\displaystyle{ \omega }[/math] определял бы, принадлежит ли эта цепочка языку [math]\displaystyle{ L(G) }[/math].

Если допустить, что среди правил контекстно-зависимой грамматики есть только одно [math]\displaystyle{ e }[/math]-правило (не снимая с грамматики остальных ограничений), то расширенный класс грамматик уже способен порождать все языки с фразовой структурой. Этот более широкий класс обладает более слабым свойством так называемой рекурсивной перечислимости, означающим существование алгоритма порождения всех цепочек данного языка и только их.

Литература

[Ахо-Ульман],

[Касьянов/95]

@@ Строка 1: / Строка 1: @@
-'''Иерархия Хомского''' (''Chomsky hierarchy'') -
+'''Иерархия Хомского''' (''[[Chomsky hierarchy]]'') - четыре типа [[грамматика|грамматик]] и [[язык|языков]]: ''[[праволинейная грамматика|праволинейные]], [[контекстно-свободная грамматика|контекстно-свободные]],[[контекстно-зависимая грамматика|контекстно-зависимые]], составляющих''.
-четыре типа грамматик и
-языков: ''праволинейные, контекстно-свободные,контекстно-зависимые, составляющих''.
-Заметим, что согласно определению каждая праволинейная
+Заметим, что согласно определению каждая [[праволинейная грамматика]] контекстно-свободная, но контекстно-свободная грамматика, содержащая ''[[e-правило|<math>e</math>-правила]]'', не является
-грамматика контекстно-свободная, но контекстно-свободная
-грамматика, содержащая ''<math>e</math>-правила'', не является
 контекстно-зависимой.
-Запрещение <math>e</math>-правил в контекстно-зависимой грамматике
+Запрещение <math>e</math>-правил в контекстно-зависимой грамматике вызвано желанием гарантировать так называемую ''рекурсивность'' порождаемого ею языка.
-вызвано желанием гарантировать так называемую
+Иначе говоря, желанием иметь алгоритм, который для произвольной контекстно-зависимой грамматики <math>G</math> и входной [[цепочка|цепочки]] <math>\omega</math> определял бы, принадлежит ли эта цепочка языку <math>L(G)</math>.
-''рекурсивность'' порождаемого ею языка.
-Иначе говоря, желанием иметь алгоритм, который для произвольной
-контекстно-зависимой грамматики <math>G</math> и входной цепочки <math>\omega</math>
-определял бы, принадлежит ли эта цепочка языку <math>L(G)</math>.
-Если допустить, что среди правил контекстно-зависимой грамматики есть
+Если допустить, что среди правил контекстно-зависимой грамматики есть только одно <math>e</math>-правило (не снимая с грамматики остальных ограничений), то расширенный класс грамматик уже способен порождать все языки с фразовой структурой. Этот более широкий класс обладает более слабым свойством так называемой ''рекурсивной перечислимости'', означающим существование алгоритма
-только одно <math>e</math>-правило (не снимая с грамматики остальных
-ограничений), то расширенный класс грамматик уже способен порождать
-все языки с фразовой структурой. Этот более широкий класс
-обладает более слабым свойством так называемой ''рекурсивной перечислимости'', означающим существование алгоритма
 порождения всех цепочек данного языка и только их.
 ==Литература==

Иерархия Хомского: различия между версиями

Версия от 11:23, 23 октября 2009

Литература

Навигация

Поиск