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

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

История

Иерархия была впервые описана Ноамом Хомским в 1956 году в статье «Три модели описания языка» (Three Models for the Description of Language), а затем развита в его книге «Синтаксические структуры» (1957). Хомский, работая в области теоретической лингвистики, стремился создать математическую модель, способную описать структуру естественных языков (например, английского). Однако его классификация оказалась универсальной и была быстро адаптирована в информатике. В 1959 году Хомский совместно с Джорджем Миллером уточнил связь между грамматиками и автоматами. В 1960-х годах иерархия стала основой для теории компиляторов, в частности, для синтаксического анализа.

Классы иерархии

Иерархия Хомского включает четыре типа грамматик (и соответствующих им языков), обозначаемых римскими цифрами от 0 до 3. Каждый тип накладывает ограничения на вид правил вывода (продукций) в грамматике. Чем выше номер типа, тем более строгие ограничения и тем менее выразителен язык.

Тип 0: Неограниченные грамматики (грамматики общего вида)

• Определение: Грамматики, на правила вывода которых не накладывается никаких ограничений, кроме того, что левая часть правила содержит хотя бы один нетерминальный символ.
• Правила: α → β, где α и β — произвольные цепочки символов (терминалов и нетерминалов), причём α не пуста.
• Порождаемые языки: Рекурсивно перечислимые языки. Это самый широкий класс, включающий все языки, которые могут быть сгенерированы формальной грамматикой.
• Распознающее устройство: Машина Тьюринга (детерминированная или недетерминированная). Язык является рекурсивно перечислимым, если существует машина Тьюринга, которая останавливается и принимает все цепочки языка, но может не останавливаться на цепочках, не принадлежащих языку.
• Примеры: Любой формальный язык, который можно описать алгоритмом, включая языки, требующие полной вычислительной мощности машины Тьюринга. Например, язык, состоящий из всех цепочек, являющихся кодами останавливающихся машин Тьюринга.

Тип 1: Контекстно-зависимые грамматики

• Определение: Грамматики, в которых каждое правило имеет вид αAβ → αγβ, где A — нетерминал, α и β — контекстные цепочки (могут быть пустыми), а γ — непустая цепочка символов. Правило может применяться только в том случае, если A находится в окружении α и β (контекст).
• Правила: αAβ → αγβ, при этом длина γ не меньше длины A (γ не пуста). Допускается правило S → ε (пустая цепочка), если S не встречается в правых частях других правил.
• Порождаемые языки: Контекстно-зависимые языки. Это подмножество рекурсивно перечислимых языков.
• Распознающее устройство: Линейно ограниченный автомат (недетерминированная машина Тьюринга с лентой, длина которой линейно ограничена длиной входной цепочки).
• Примеры: Язык {aⁿbⁿcⁿ | n ≥ 1} (равное количество a, b и c). Этот язык не является контекстно-свободным, но может быть описан контекстно-зависимой грамматикой. В естественных языках некоторые конструкции (например, швейцарский немецкий) требуют контекстно-зависимых правил.

Тип 2: Контекстно-свободные грамматики

• Определение: Грамматики, в которых каждое правило имеет вид A → γ, где A — нетерминал, а γ — произвольная цепочка символов (терминалов и нетерминалов). Правило не зависит от контекста, в котором находится A.
• Правила: A → γ.
• Порождаемые языки: Контекстно-свободные языки. Это подмножество контекстно-зависимых языков.
• Распознающее устройство: Недетерминированный автомат с магазинной памятью (стековый автомат). Детерминированные контекстно-свободные языки распознаются детерминированными автоматами с магазинной памятью.
• Примеры: Язык {aⁿbⁿ | n ≥ 1} (равное количество a и b). Большинство синтаксических конструкций языков программирования (например, вложенные скобки, арифметические выражения) описываются контекстно-свободными грамматиками. В лингвистике контекстно-свободные грамматики используются для описания структуры фраз (синтаксиса) естественных языков, хотя существуют исключения (например, в языках с перекрёстными зависимостями).

Тип 3: Регулярные грамматики (автоматные грамматики)

• Определение: Грамматики, в которых каждое правило имеет один из двух видов: A → aB (праволинейная) или A → Ba (леволинейная), где A и B — нетерминалы, a — терминал. Также допускается правило A → ε (пустая цепочка) или A → a.
• Правила: A → aB или A → a (для праволинейной грамматики).
• Порождаемые языки: Регулярные языки. Это подмножество контекстно-свободных языков.
• Распознающее устройство: Конечный автомат (детерминированный или недетерминированный). Регулярные языки также могут быть описаны регулярными выражениями.
• Примеры: Язык {aⁿ | n ≥ 0} (последовательность a любой длины). Лексика языков программирования (идентификаторы, числа, ключевые слова) обычно описывается регулярными грамматиками. В естественных языках регулярные грамматики могут описывать простые морфологические структуры, но не синтаксис предложений.

Связь с автоматами

Каждому типу грамматики соответствует определённый класс абстрактных вычислительных устройств (автоматов), которые могут распознавать языки этого типа:

Эта связь является фундаментальной: чем проще автомат, тем более ограничен класс языков, которые он может распознать. Например, конечный автомат не может распознать язык {aⁿbⁿ}, так как для подсчёта количества a требуется неограниченная память, которую предоставляет магазинный автомат.

Применение

Иерархия Хомского имеет широкое практическое применение в различных областях:

• Компиляторостроение: Лексический анализ (регулярные грамматики, тип 3) и синтаксический анализ (контекстно-свободные грамматики, тип 2) являются стандартными этапами компиляции. Контекстно-зависимые грамматики используются реже, например, для семантического анализа (проверка типов).
• Лингвистика: Иерархия используется для классификации естественных языков по их сложности. Хомский утверждал, что естественные языки являются контекстно-свободными (с некоторыми оговорками), хотя существуют исследования, показывающие необходимость контекстно-зависимых правил.
• Теория вычислений: Иерархия помогает понять границы вычислимости. Например, проблема остановки для машины Тьюринга неразрешима, что связано с типом 0.
• Биоинформатика: Регулярные и контекстно-свободные грамматики используются для моделирования структуры РНК и ДНК.
• Обработка естественного языка: Контекстно-свободные грамматики лежат в основе многих синтаксических анализаторов (парсеров) для английского, русского и других языков.

Критика и ограничения

Иерархия Хомского, несмотря на свою фундаментальность, подвергалась критике в нескольких аспектах:

• Неполнота для естественных языков: Некоторые лингвисты, такие как Джеральд Газдар, утверждали, что естественные языки могут быть описаны более простыми грамматиками (например, контекстно-свободными), в то время как другие (например, Стюарт Шабер) приводили примеры, требующие контекстно-зависимых правил (например, в швейцарском немецком).
• Отсутствие учёта семантики: Иерархия описывает только синтаксическую структуру, игнорируя значение. Язык может быть синтаксически правильным, но бессмысленным.
• Практическая сложность: Контекстно-зависимые грамматики (тип 1) редко используются на практике из-за высокой вычислительной сложности распознавания (NP-полные задачи в некоторых случаях).
• Альтернативные классификации: Существуют другие способы классификации языков, например, по сложности распознавания (P, NP, PSPACE) или по типу порождающих механизмов (грамматики Линденмайера, грамматики с ограничениями).

Интересные факты

• Иерархия Хомского иногда называется «иерархией Хомского — Шютценберже» в честь Марселя-Поля Шютценберже, который внёс вклад в её формализацию.
• Контекстно-свободные грамматики (тип 2) являются основой для большинства языков программирования, включая C, Java, Python и Rust.
• Регулярные языки (тип 3) могут быть описаны регулярными выражениями, которые широко используются в текстовых редакторах и утилитах (например, grep).
• В 1960-х годах Хомский предположил, что естественные языки являются контекстно-свободными, но позже были найдены контрпримеры, такие как языки с перекрёстными зависимостями (например, в нидерландском).

Источники

• Chomsky, N. (1956). Three models for the description of language. IRE Transactions on Information Theory, 2(3), 113-124.
• Chomsky, N. (1959). On certain formal properties of grammars. Information and Control, 2(2), 137-167.
• Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley.
• Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
• Шабер, С. (1985). Evidence for context-sensitive grammar in natural language. Linguistic Inquiry, 16(3), 333-363.