EssayAI
Блог
Блог
Естественные науки

Иерархия Хомского: типы грамматик и автоматы

8 ноября 2026Время чтения: 9 минут
#иерархия Хомского#формальные языки#грамматики#теория автоматов#теория вычислений
Иерархия Хомского: типы грамматик и автоматы

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

Ниже сравним все четыре уровня и разберём, почему классификация конкретной грамматики и поиск минимального класса языка - разные задачи. Сначала выберите пример: инструмент поможет построить объяснение и проверить ход рассуждения.

Язык, грамматика и вложенность классов

Формальный алфавит - конечный набор символов, например {a,b}\{a,b\}. Слово - конечная последовательность этих символов; пустое слово обозначают ε\varepsilon. Язык - множество слов над алфавитом, в том числе, возможно, бесконечное. Например, a∗b∗a^*b^* состоит из любого числа букв aa, за которыми следует любое число букв bb.

Грамматика задаёт язык при помощи конечного набора правил. Помимо терминалов, которые остаются в готовом слове, она использует нетерминалы - вспомогательные символы, подлежащие замене. Вывод начинается со стартового символа SS и заканчивается, когда остаются только терминалы. Скажем, правила S→aSbS \to aSb и S→εS \to \varepsilon порождают ε\varepsilon, abab, aabbaabb и другие слова вида anbna^n b^n при n≥0n \ge 0.

Маркер проходит по выводу слова aabb: два применения правила добавляют парные буквы, затем S заменяется пустым словом. Обратное движение возвращает маркер к началу примера.

Четыре класса принято нумеровать в обратном порядке от ограниченного к общему: тип 3 ⊊ тип 2 ⊊ тип 1 ⊊ тип 0. Включения строгие: на каждом переходе появляются языки, которых на предыдущем уровне нет. Такую последовательность ограничений Хомский исследовал в работе 1959 года.

Тип 3: регулярные языки

В праволинейной грамматике правила имеют вид A→aBA \to aB, A→aA \to a и, в принятой конвенции, могут включать завершение A→εA \to \varepsilon. Здесь AA и BB - нетерминалы, aa - терминал. Леволинейные правила дают тот же класс, но смешивать направления произвольно нельзя: такая грамматика уже не обязательно регулярна.

Регулярные языки распознаёт конечный автомат. Его состояние хранит лишь одно из конечного числа возможных состояний; отдельной неограниченной памяти у модели нет. Например, автомат для a∗b∗a^*b^* помнит, начались ли уже буквы bb, и отвергает aa после этого момента. Связь с регулярными выражениями раскрывает теорема Клини.

Тип 2: контекстно-свободные языки

У контекстно-свободного правила слева стоит ровно один нетерминал: A→γA \to \gamma, где γ\gamma - строка терминалов и нетерминалов, возможно пустая. Правило применимо независимо от соседей этого вхождения AA. Поэтому грамматика для anbna^n b^n выше относится к типу 2: правило S→aSbS \to aSb не является праволинейным, но слева у него один нетерминал.

Язык {anbn∣n≥0}\{a^n b^n \mid n \ge 0\} не регулярен. Интуиция такова: число первых букв не ограничено, а конечному автомату нужно было бы различать сколь угодно много значений, чтобы проверить равное число вторых. Формально это доказывают, например, леммой о накачке или теоремой Майхилла - Нероуда; нескольких проверенных слов для доказательства недостаточно.

Соответствующая модель - недетерминированный магазинный автомат. В этом примере он кладёт символ в стек на каждой aa, затем снимает по одному на каждой bb. Порядок блоков и пустота стека помогают проверить равенство. Стек допускает вложенность, но доступен только с вершины; детерминированные магазинные автоматы распознают не все контекстно-свободные языки.

Как доказать, что примера типа 3 недостаточно

Для языка парных блоков можно провести короткое доказательство от противного с помощью леммы о накачке. Предположим, что он регулярен, и обозначим через pp соответствующую длину накачки. Выберем слово из pp букв aa, за которыми идут pp букв bb. Лемма утверждает, что его можно разбить на три части так, чтобы средняя часть была непуста, первые две вместе имели длину не более pp, а повторение средней части любое число раз оставляло слово в языке.

Но первые pp позиций заняты только буквами aa. Значит, средняя часть любого допустимого разбиения состоит только из них. Если удалить её, букв aa станет меньше, чем букв bb; полученное слово уже не принадлежит исходному языку. Противоречие показывает, что конечного автомата для всего языка не существует. Порядок кванторов здесь важен: нужно исключить каждое допустимое разбиение выбранного слова, а не только одно удобное.

Это доказательство устанавливает нижнюю границу, а приведённая выше грамматика - верхнюю. Вместе они дают точный ответ: минимальный класс языка в рассматриваемой иерархии - тип 2. Для отдельного конечного набора слов рассуждение было бы другим: любой конечный язык регулярен, поскольку автомат может хранить достаточно состояний для всех его слов.

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

Типичное правило контекстно-зависимой грамматики имеет форму αAβ→αγβ\alpha A\beta \to \alpha\gamma\beta: заменить AA на непустую строку γ\gamma можно в указанном окружении α\alpha и β\beta. Эквивалентная по порождаемым языкам формулировка использует неукорачивающие правила: правая часть не короче левой. Для пустого слова допускают специальное исключение S→εS \to \varepsilon, если стартовый символ не появляется справа.

Классический пример языка этого уровня - {anbncn∣n≥1}\{a^n b^n c^n \mid n \ge 1\}. В нём три последовательных блока одинаковой длины. Он контекстно-зависим, но не контекстно-свободен: для второго утверждения требуется доказательство, например лемма о накачке для контекстно-свободных языков. Просто указать, что «нужны два счётчика», полезно для интуиции, но недостаточно как доказательство.

Типу 1 соответствует недетерминированный линейно ограниченный автомат: вариант машины Тьюринга, использующий объём ленты, ограниченный линейной функцией длины входа. Его рабочая память растёт вместе со словом, но не произвольно. В отличие от одного стека, лента позволяет возвращаться к разным позициям и менять пометки.

Четыре класса языков и соответствующие им распознающие модели: от конечного автомата до машины Тьюринга
Четыре класса языков и соответствующие им распознающие модели: от конечного автомата до машины Тьюринга

Тип 0: перечислимые языки

Грамматики типа 0 называют неограниченными: в правилах α→β\alpha \to \beta левая часть содержит хотя бы один нетерминал, а правая может быть произвольной строкой. Они порождают вычислимо перечислимые языки. Их распознаёт машина Тьюринга: для слова из языка она когда-нибудь остановится с принятием, а для слова вне языка может отвергнуть его или работать бесконечно.

Это различие принципиально. Разрешимый язык имеет алгоритм, который останавливается с правильным ответом на любом входе. Каждый разрешимый язык перечислим, но не каждый перечислимый разрешим. Поэтому машина, распознающая язык типа 0, не обязана всегда выдавать ответ «нет». Об устройстве модели и кодировании вычислений рассказывает статья про универсальную машину Тьюринга; недетерминированная машина помогает отдельно разобраться с ветвлением вычислений.

Как определить тип в задаче

Сначала выпишите правила целиком и проверьте ограничения по порядку: праволинейность, один нетерминал слева, неукорачивание с учётом исключения для ε\varepsilon. Если вся грамматика удовлетворяет правилам типа 3, она подходит и под более общие классы. В учебном ответе обычно называют самый ограниченный подходящий тип и обосновывают его формой каждого правила.

Затем уточните, спрашивают ли о грамматике или о языке. Одна грамматика может не иметь регулярной формы, но порождать регулярный язык: например, S→ABS \to AB, A→aA \to a, B→bB \to b - грамматика типа 2, а её язык {ab}\{ab\} конечен и потому регулярен. Вид имеющихся правил даёт верхнюю границу для класса языка, но сам по себе не доказывает минимальность. Для нижней границы понадобится отдельный аргумент о невозможности более простой модели.

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

Что иерархия говорит о практике

Выбор класса описывает выразительные возможности модели, а не гарантирует одинаковое быстродействие всех реализаций. Две грамматики одного типа могут заметно различаться удобством разбора и размером описания. Даже если синтаксическую конструкцию можно выразить более общей моделью, разработчик часто выбирает ограниченную грамматику: её легче анализировать и сопровождать.

При этом семантические ограничения программы, например соответствие имён объявлениям, обычно проверяют отдельным этапом. Поэтому вопрос «какой класс у языка программирования целиком» нельзя решить одной ссылкой на грамматику синтаксиса: сначала нужно договориться, какие именно строки и какие проверки включены в определение языка. Для учебной задачи такая договорённость столь же важна, как выбор алфавита и указание, входит ли пустое слово.

Частые ошибки

  • Переворачивать включения. Каждый регулярный язык контекстно-свободен, но не наоборот.
  • Считать ограничение правила свойством языка. Другая грамматика может породить тот же язык и иметь более простой тип.
  • Забывать пустое слово. При определении типа 1 нужно явно указать принятую конвенцию и исключение для S→εS \to \varepsilon.
  • Путать распознавание с разрешением. Машина для языка типа 0 может не остановиться на слове вне языка.
  • Доказывать неравенство классов набором примеров. Для отрицательного утверждения нужен общий аргумент, а не проверка нескольких длин.

FAQ

Все ли контекстно-свободные языки регулярны?

Нет. Язык {anbn∣n≥0}\{a^n b^n \mid n \ge 0\} контекстно-свободен, но не регулярен. При этом любой регулярный язык входит в контекстно-свободный класс.

Почему для типа 2 указан недетерминированный автомат?

Потому что именно недетерминированные магазинные автоматы распознают весь класс контекстно-свободных языков. Детерминированные распознают его собственный подкласс.

Всегда ли можно по правилам найти минимальный класс языка?

Нет. Проверка формы правил определяет тип данной грамматики и даёт верхнюю границу для её языка. Чтобы установить минимальный класс, может потребоваться другое представление языка и доказательство исключения более узких классов.

Коротко

Иерархия Хомского связывает ограничения грамматик с выразительной силой моделей: регулярные языки распознают конечные автоматы, контекстно-свободные - автоматы со стеком, контекстно-зависимые - линейно ограниченные автоматы, вычислимо перечислимые - машины Тьюринга. Для задачи важно отдельно классифицировать заданные правила и обосновать минимальный класс порождаемого ими языка.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Магазинный автомат: стек, переходы и примеры

Магазинный автомат: стек, переходы и примеры

Магазинный автомат простыми словами: как состояние и стек управляют переходами, как разобрать скобки и язык aⁿbⁿ, чем различаются условия принятия и связь с грамматиками.

8 ноября 20268 минут
Машина Тьюринга недетерминированная: модель и сила

Машина Тьюринга недетерминированная: модель и сила

Машина Тьюринга недетерминированная (НМТ): чем отличается от детерминированной, как работает дерево вычислений, почему она не сильнее по разрешимости и при чём тут класс NP.

5 мая 20267 минут
Контекстно-свободная грамматика: правила и примеры

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

Контекстно-свободная грамматика простыми словами: терминалы и нетерминалы, вывод слова, дерево разбора, неоднозначность и применение при анализе синтаксиса.

8 ноября 20269 минут
Регулярная грамматика: правила, примеры и автомат

Регулярная грамматика: правила, примеры и автомат

Регулярная грамматика простыми словами: как устроены праволинейные правила, как вывести слово, построить конечный автомат и проверить границы модели на примерах.

8 ноября 20269 минут
Автоматы Мура и Мили: отличия, формулы и примеры

Автоматы Мура и Мили: отличия, формулы и примеры

Автоматы Мура и Мили простыми словами: чем отличаются выходы, как строить граф и таблицу переходов, как преобразовать один тип в другой и почему выходные строки сдвинуты на такт.

11 июня 20268 минут
Теорема Клини: регулярные языки и автоматы

Теорема Клини: регулярные языки и автоматы

Теорема Клини простыми словами: почему регулярные выражения, конечные автоматы и регулярные языки описывают один и тот же класс, как доказывают эквивалентность и где это применяют.

19 июня 20267 минут