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

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

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

Грамматика как генератор языка

До сих пор мы описывали язык множеством («все строки чётной длины»). Второй способ — порождающая грамматика: набор правил-подстановок, которые из стартового символа выводят все строки языка. Грамматика — это четвёрка (V, Σ, P, S): нетерминалы V (вспомогательные символы), терминалы Σ (символы алфавита), правила P вида «левая часть → правая часть» и стартовый символ S. Применяя правила, мы выводим строки.

Ноам Хомский в 1956 году заметил: ограничивая форму правил, мы получаем ровно четыре класса языков, и каждому соответствует своя машина-распознаватель. Это и есть мост между грамматиками (генераторы) и автоматами (распознаватели) — центральная идея курса.

Четыре типа

Тип	Класс языков	Форма правил	Машина
3	регулярные	A → aB или A → a	конечный автомат
2	контекстно-свободные	A → γ (одиночный нетерминал слева)	магазинный автомат
1	контекстно-зависимые	αAβ → αγβ	линейно-ограниченный автомат
0	рекурсивно-перечислимые	любые правила	машина Тьюринга

Классы строго вложены: регулярные ⊂ КС ⊂ контекстно-зависимые ⊂ рекурсивно-перечислимые. Чем меньше номер типа, тем мощнее класс и слабее ограничения на правила.

┌──────────────────────────────────────────┐
│ тип 0: рекурсивно-перечислимые (Тьюринг)  │
│ ┌──────────────────────────────────────┐ │
│ │ тип 1: контекстно-зависимые          │ │
│ │ ┌──────────────────────────────────┐ │ │
│ │ │ тип 2: контекстно-свободные      │ │ │
│ │ │ ┌──────────────────────────────┐ │ │ │
│ │ │ │ тип 3: регулярные            │ │ │ │
│ │ │ └──────────────────────────────┘ │ │ │
│ │ └──────────────────────────────────┘ │ │
│ └──────────────────────────────────────┘ │
└──────────────────────────────────────────┘

Пример вывода в грамматике

Возьмём КС-грамматику для языка aⁿbⁿ (n ≥ 1): S → aSb | ab. Один вывод: S ⇒ aSb ⇒ aabb. Покажем порождение программно — заменяя S по правилу, пока не останется нетерминалов.

# грамматика: S -> aSb | ab
def derive(steps):
    s = "S"
    out = [s]
    for _ in range(steps):
        if "S" in s:
            s = s.replace("S", "aSb", 1)  # рекурсивное правило
        out.append(s)
    # завершаем выводом S -> ab
    s = s.replace("S", "ab", 1)
    out.append(s)
    return out

for form in derive(2):
    print(form)

Вывод:

S
aSb
aaSbb
aaabbb

Каждая стрелка ⇒ — применение одного правила. Финальная строка aaabbb принадлежит языку aⁿbⁿ.

Как работает под капотом

Почему форма правил определяет мощность? Регулярные правила (A → aB) при выводе всегда держат ровно один нетерминал на конце — это в точности «состояние» конечного автомата без памяти. КС-правила (A → γ) допускают вложенность: нетерминал в середине порождает «скобочную» структуру, для которой нужен стек. Контекстно-зависимые правила могут смотреть на окружение (α, β) и не укорачивают строку — это даёт линейно-ограниченную память. Тип 0 не ограничен ничем — отсюда полная мощь Тьюринга и, как следствие, неразрешимость.

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

Думать, что больший номер типа = мощнее. Наоборот: тип 0 самый мощный, тип 3 самый слабый. Номер растёт с усилением ограничений.

Считать включения нестрогими. Включения строгие: есть КС-язык, не являющийся регулярным (aⁿbⁿ), и контекстно-зависимый, не являющийся КС (aⁿbⁿcⁿ). Мы докажем это леммами о накачке.

Путать порождение и распознавание. Грамматика порождает строки, автомат проверяет принадлежность. Это две стороны одного класса языков.

Итог

Грамматика (V, Σ, P, S) порождает язык подстановками от стартового символа.
Иерархия Хомского: типы 3 ⊂ 2 ⊂ 1 ⊂ 0 — регулярные, КС, контекстно-зависимые, рекурсивно-перечислимые.
Каждому типу соответствует машина: конечный автомат, магазинный, ЛО-автомат, машина Тьюринга.
Меньший номер типа — слабее ограничения и мощнее класс; включения строгие.