Грамматики Хомского

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

В основе иерархии лежит идея о том, что любой формальный язык (множество строк над некоторым алфавитом) может быть порождён грамматикой определённого типа. Тип грамматики определяется ограничениями на вид правил подстановки (продукций), используемых для построения строк. Хомский выделил четыре типа грамматик, образующих иерархию, где каждый последующий тип является подмножеством предыдущего: грамматики типа 0 (неограниченные), типа 1 (контекстно-зависимые), типа 2 (контекстно-свободные) и типа 3 (регулярные). Эта иерархия имеет фундаментальное значение в теории формальных языков, лингвистике, информатике и вычислительной технике.

История возникновения

Идея формализации грамматик естественного языка возникла в контексте развития структурной лингвистики и кибернетики в середине XX века. Ноам Хомский, работая в Массачусетском технологическом институте, стремился создать математическую модель, которая бы объясняла способность человека порождать и понимать бесконечное множество предложений на родном языке при помощи конечного набора правил.

В 1956 году Хомский опубликовал статью «Three Models for the Description of Language», а в 1957 году — книгу «Syntactic Structures», где впервые изложил основы генеративной (порождающей) грамматики. Ключевым нововведением стало различие между поверхностной и глубинной структурами предложения, а также введение правил трансформации. В 1958 году на симпозиуме по теории информации Хомский совместно с Марселем-Полем Шютценберже представил классификацию формальных грамматик, которая получила название иерархии Хомского. Эта работа заложила основы теории формальных языков, отделив лингвистику от чисто описательных методов и сблизив её с математикой и информатикой.

Типы грамматик в иерархии Хомского

Каждый тип грамматики отличается набором разрешённых правил подстановки. Грамматика формально определяется как четверка \( G = (N, \Sigma, P, S) \), где:

• \( N \) — конечное множество нетерминальных символов (переменных, обозначающих синтаксические категории, например, «существительное», «глагольная группа»);
• \( \Sigma \) — конечное множество терминальных символов (основных единиц, например, слов или букв);
• \( P \) — конечное множество правил подстановки (продукций) вида \( \alpha \rightarrow \beta \), где \( \alpha \) и \( \beta \) — строки из символов;
• \( S \) — начальный (аксиоматический) символ из \( N \), с которого начинается порождение.

Тип 0: Неограниченные грамматики

Грамматики типа 0 являются самыми общими. На правила подстановки \( \alpha \rightarrow \beta \) не накладывается никаких ограничений, кроме того, что \( \alpha \) не может быть пустой строкой. Эти грамматики могут порождать любые рекурсивно перечислимые языки. Они обладают максимальной выразительной силой, но их анализ практически неразрешим — невозможно в общем случае определить, принадлежит ли произвольная строка языку, порождённому такой грамматикой. В практическом программировании грамматики типа 0 используются крайне редко из-за недетерминированности.

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

В грамматиках типа 1 правила имеют вид \( \alpha A \beta \rightarrow \alpha \gamma \beta \), где \( A \) — нетерминальный символ, а \( \alpha \) и \( \beta \) — контекстные строки (могут быть пустыми), \( \gamma \) — непустая строка. Иными словами, замена нетерминала \( A \) на строку \( \gamma \) возможна только в определённом контексте — когда слева от \( A \) стоит \( \alpha \), а справа — \( \beta \). Такие грамматики порождают контекстно-зависимые языки. Они позволяют описать конструкции, где важен порядок слов и их согласование, например, в естественных языках — согласование подлежащего и сказуемого в числе и роде. Однако анализ КЗ-языков требует экспоненциального времени, поэтому в компьютерной лингвистике и программировании они применяются ограниченно.

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

Грамматики типа 2 — наиболее распространённый и практически значимый класс. Правила имеют вид \( A \rightarrow \gamma \), где \( A \) — один нетерминальный символ, а \( \gamma \) — любая строка (в том числе пустая) из терминалов и нетерминалов. Замена происходит независимо от контекста — отсюда название «контекстно-свободные». Эти грамматики порождают контекстно-свободные языки.

КС-грамматики играют центральную роль в теории компиляторов и синтаксическом анализе. Большинство языков программирования (C, Java, Python) описываются именно с помощью КС-грамматик (часто в форме Бэкуса — Наура). В лингвистике КС-грамматики использовались для описания структуры предложений естественных языков, хотя для некоторых явлений (например, перекрёстных зависимостей) их выразительной силы недостаточно. Анализ КС-языков возможен за полиномиальное время (обычно \( O(n^3) \)), что делает их практичными.

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

Грамматики типа 3 — самый ограниченный класс. Правила имеют вид \( A \rightarrow aB \) или \( A \rightarrow a \) (праволинейные) либо \( A \rightarrow Ba \) (леволинейные), где \( A, B \) — нетерминалы, \( a \) — терминал. Регулярные грамматики порождают регулярные языки, которые также могут быть описаны с помощью регулярных выражений или конечных автоматов.

Регулярные языки используются для лексического анализа, разбора простых шаблонов, в текстовых редакторах (поиск и замена), в сетевых протоколах. Однако их выразительная сила ограничена — они не могут описывать вложенные структуры, такие как скобочные выражения (например, арифметические формулы с произвольной вложенностью скобок). Для этого требуются контекстно-свободные грамматики.

Значение и приложения

Иерархия Хомского стала одним из краеугольных камней теоретической информатики. Она позволила:

• Классифицировать языки по сложности задач разбора (распознавания).
• Разработать эффективные алгоритмы синтаксического анализа для каждого уровня (например, LL- и LR-анализаторы для КС-грамматик).
• Определить границы применимости различных средств формального описания (регулярные выражения, контекстно-свободные грамматики, машины Тьюринга).

Критика и развитие

Сам Хомский впоследствии отошёл от иерархической классификации в своей лингвистической теории, сосредоточившись на минималистской программе, где грамматика рассматривается как система универсальных принципов и параметров. Критики отмечали, что иерархия Хомского слишком груба для точного описания естественных языков, где многие явления требуют контекстно-зависимых или даже более сложных механизмов. В современной компьютерной лингвистике популярность получили статистические и нейросетевые методы (например, трансформеры), которые не опираются напрямую на формальные грамматики, хотя принципы иерархии остаются важными для понимания вычислительной сложности задач обработки языка.

Примеры

Пример регулярной грамматики (тип 3)

Порождает все строки вида ab* (a, за которой следует любое число b, включая ноль):

• S → aA
• A → bA
• A → ε (пустая строка)

Пример контекстно-свободной грамматики (тип 2)

Порождает правильные скобочные последовательности:

• S → SS
• S → (S)
• S → ε

Пример контекстно-зависимой грамматики (тип 1)

Порождает язык a^n b^n c^n (строки, состоящие из одинакового числа символов a, b, c):

• S → aSBC
• S → aBC
• CB → BC
• aB → ab
• bB → bb
• bC → bc
• cC → cc

(На практике для этого языка проще использовать грамматику типа 0 или неконтекстно-свободные правила.)

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

• Иерархия Хомского соответствует различным классам автоматов: тип 3 — конечные автоматы, тип 2 — автоматы с магазинной памятью, тип 1 — линейно ограниченные автоматы, тип 0 — машины Тьюринга.
• Сам Хомский первоначально выделил три типа (0, 1, 2), а регулярные грамматики (тип 3) были добавлены позже при совместной работе с Шютценберже.
• В программировании практически все современные языки являются контекстно-свободными, но из-за встроенных ограничений (например, объявление переменных перед использованием) их полный синтаксический анализ может требовать контекстно-зависимых правил.

Источники

• Хомский Н. «Синтаксические структуры» (1957)
• Chomsky N., Schützenberger M. P. «The Algebraic Theory of Context-Free Languages» (1963)
• Хопкрофт Дж., Мотвани Р., Ульман Дж. «Введение в теорию автоматов, языков и вычислений» (2001)
• Сэлломей Д. «Вычислительная сложность формальных языков» (1994)