Иерархия Хомского: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Иерархия Хомского''' (''[[Chomsky hierarchy]]'') | '''Иерархия Хомского''' (''[[Chomsky hierarchy]]'') — четыре типа [[грамматика|грамматик]] и [[язык|языков]]: ''[[праволинейная грамматика|праволинейные]], [[контекстно-свободная грамматика|контекстно-свободные]],[[контекстно-зависимая грамматика|контекстно-зависимые]], составляющих''. | ||
Заметим, что согласно определению каждая [[праволинейная грамматика]] контекстно-свободная, но контекстно-свободная грамматика, содержащая ''[[e- | Заметим, что согласно определению каждая [[праволинейная грамматика]] контекстно-свободная, но контекстно-свободная грамматика, содержащая ''[[e-Правило|<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>-правило (не снимая с грамматики остальных ограничений), то расширенный класс грамматик уже способен порождать все языки с фразовой структурой. Этот более широкий класс обладает более слабым свойством так называемой ''рекурсивной перечислимости'', означающим существование алгоритма | ||
порождения всех цепочек данного языка и только их. | порождения всех цепочек данного языка и только их. | ||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
Текущая версия от 11:30, 21 февраля 2011
Иерархия Хомского (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]-правило (не снимая с грамматики остальных ограничений), то расширенный класс грамматик уже способен порождать все языки с фразовой структурой. Этот более широкий класс обладает более слабым свойством так называемой рекурсивной перечислимости, означающим существование алгоритма порождения всех цепочек данного языка и только их.
Литература
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
- Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.