Введение

Иерархия классов формальных грамматик

Иерархия Чомского (редко называемая иерархией Чомского-Шюценбергера) в области теории формальных языков, информатики и лингвистики представляет собой иерархию классов формальных грамматик. Формальная грамматика описывает, как формировать строки из словарного запаса (или алфавита) языка, которые соответствуют синтаксису этого языка. Лингвист Ноам Хомский предположил существование четырех различных классов формальных грамматик, способных генерировать языки возрастающей сложности. Каждый класс также может полностью генерировать языки всех подлежащих ему классов (по включению).

История

Общая идея иерархии грамматик была впервые описана Ноамом Хомским в работе "Три модели описания языка". Марсель Поль Шюценбергер также внес вклад в развитие теории формальных языков; в статье "Алгебраическая теория контекстно-свободных языков" описывается современная иерархия, включая контекстно-свободные грамматики. Параллельно с лингвистами, математики разрабатывали модели вычислений (с помощью автоматов). Синтаксический анализ предложения в языке аналогичен вычислениям, и грамматики, описанные Хомским, оказались как схожими, так и эквивалентными по вычислительной мощности различным моделям машин.

Рекурсивно перечисляемые грамматики (тип 0)

Грамматики типа 0 включают в себя все формальные грамматики. На правила вывода не накладывается никаких ограничений. Они порождают ровно все языки, которые могут быть распознаны машиной Тьюринга, таким образом, любой порождаемый язык может быть порожден грамматикой типа 0. Следует отметить, что это отличается от рекурсивных языков, которые могут быть определены машиной Тьюринга, всегда завершающей свою работу.