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

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

Заметим, что согласно определению каждая праволинейная грамматика контекстно-свободная, но контекстно-свободная грамматика, содержащая $e$-правила, не является контекстно-зависимой.

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

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

Литература

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

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