Иерархия Хомского

Иерархия Хомского (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.