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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Иерархия Хомского''' (''Chomsky hierarchy'') - четыре типа грамматик и языков: ''право...)
 
Нет описания правки
Строка 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>-правило (не снимая с грамматики остальных
ограничений), то расширенный класс грамматик уже способен порождать
все языки с фразовой структурой. Этот более широкий класс
обладает более слабым свойством так называемой ''рекурсивной перечислимости'', означающим существование алгоритма
порождения всех цепочек данного языка и только их.
порождения всех цепочек данного языка и только их.
==Литература==
==Литература==

Навигация