Нормальная форма Хомского

Нормальная форма Хомского — это «причёсанная» КС-грамматика, где все правила имеют один из двух простых видов. Она удобна для алгоритмов и доказательств.

Нормальная форма Хомского (CNF): грамматика, где каждое правило либо A → BC (два нетерминала), либо A → a (один терминал); допускается S → ε, если язык содержит пустую строку.

Зачем нормализовать

КС-грамматики бывают «грязными»: длинные правые части, ε-правила, цепные правила A → B, бесполезные символы. Для теории и алгоритмов это неудобно. CNF приводит всё к двум формам, что даёт два бонуса. Во-первых, дерево разбора в CNF бинарно (каждый внутренний узел имеет ровно двух детей) — это упрощает доказательства (например, лемму о накачке). Во-вторых, на CNF работает классический алгоритм разбора CYK за время O(n³), который проверяет принадлежность строки языку для любой КС-грамматики.

Замечательный факт: любую КС-грамматику можно привести к эквивалентной CNF (порождающей тот же язык, возможно, без ε). Преобразование всегда возможно — это конструктивная теорема.

Шаги приведения к CNF

Проверка формы правил программно

Напишем проверку, что грамматика уже в CNF: каждое правило — либо два нетерминала, либо один терминал.

nonterminals = {"S", "A", "B", "C"}

def is_cnf_rule(left, right):
    if len(right) == 1 and right[0] not in nonterminals:
        return True                      # A -> a (терминал)
    if len(right) == 2 and all(x in nonterminals for x in right):
        return True                      # A -> BC
    return False

grammar = [
    ("S", ["A", "B"]),    # S -> AB   ✓
    ("A", ["a"]),         # A -> a    ✓
    ("B", ["C", "C"]),    # B -> CC   ✓
    ("C", ["b"]),         # C -> b    ✓
    ("S", ["A", "B", "C"]),  # S -> ABC  ✗ (три символа)
]
for left, right in grammar:
    ok = is_cnf_rule(left, right)
    arrow = " ".join(right)
    print(f"{left} -> {arrow:<8} CNF? {ok}")

Вывод:

S -> A B      CNF? True
A -> a        CNF? True
B -> C C      CNF? True
C -> b        CNF? True
S -> A B C    CNF? False

Правило S → ABC нарушает CNF (три символа справа). Шаг BIN превратил бы его в S → AE, E → BC — и грамматика стала бы корректной CNF.

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

CNF — фундамент алгоритма CYK (Кока-Янгера-Касами). CYK заполняет таблицу: для каждой подстроки определяет, какие нетерминалы её порождают, комбинируя результаты для половинок по правилам A → BC. Бинарность CNF — почему достаточно перебирать пары половинок, что и даёт куб O(n³). Это первый универсальный алгоритм разбора, работающий на любой КС-грамматике (в отличие от LL/LR, требующих ограничений). Помимо CYK, есть нормальная форма Грейбах (A → aα) для нисходящего разбора — но Хомского популярнее за бинарность.

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

Забыть про ε и старт. Если язык содержит пустую строку, её обрабатывают отдельным правилом S0 → ε, а сам старт выносят, чтобы он не встречался справа.

Считать, что CNF меняет язык. Нет: CNF порождает тот же язык (с возможным исключением — отдельной обработкой ε).

Думать, что не всякую грамматику можно нормализовать. Любая КС-грамматика приводится к CNF — это всегда возможно.

Итог

• CNF: все правила вида A → BC или A → a (плюс S0 → ε при необходимости).
• Приведение: шаги START, TERM, BIN, DEL, UNIT; любая КС-грамматика нормализуема.
• Дерево разбора в CNF бинарно — это упрощает доказательства и алгоритмы.
• На CNF работает универсальный разбор CYK за O(n³) для любой КС-грамматики.