Формальные языки

Нормальные формы: CNF и GNF

Возьмём грамматику арифметических выражений с её ε-правилами, длинными хвостами и unit-правилами. Алгоритм парсинга смотрит на неё и сдаётся: слишком много форм правил, слишком много частных случаев. Хомский в 1959 и Грейбах в 1965 предложили решение - стандартизировать форму, как промышленность стандартизировала розетки. Раз форма предсказуема, можно написать один универсальный алгоритм - например, CYK.

**Алгоритм CYK** - вход требует CNF; используется в bioinformatics для парсинга RNA-структур
**Stochastic CFG в NLP** - PCFG-парсеры (Charniak, Stanford Parser) внутренне работают с CNF-грамматиками
**Учебные курсы по теории вычислений** - доказательство pumping lemma для КС-языков идёт через CNF-дерево вывода

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

Грамматика `S -> aSb | ε` короткая, но капризная: ε-правила, длинные правые части, нетерминалы и терминалы вперемешку. Алгоритмам парсинга (как CYK) нужна предсказуемая форма. **CNF (Chomsky Normal Form)** даёт ровно две: либо правило `A -> BC` (два нетерминала), либо `A -> a` (один терминал). И допустимо одно ε-правило только для стартового нетерминала, если язык содержит пустую строку.

Любая КС-грамматика может быть преобразована к CNF. Это означает: класс КС-языков не зависит от выбора формы записи. Теоретическая ценность - доказательства теорем (pumping lemma, decidability). Практическая - алгоритм CYK работает строго на CNF-грамматиках за O(n³).

Какое правило НЕ является правилом в нормальной форме Хомского?

Алгоритм приведения к CNF

Приведение к CNF - последовательность из четырёх шагов, каждый избавляется от одного типа «нечистоты». Порядок важен: ε-правила удаляются раньше unit-правил, иначе появятся новые ε. Каждый шаг сохраняет язык, но меняет правила.

Добавить новый стартовый нетерминал S' -> S, чтобы старый S не появлялся справа
Удалить ε-правила (кроме S' -> ε для пустой строки): найти nullable нетерминалы и продублировать правила с/без них
Удалить unit-правила A -> B: заменить правила B на правила A напрямую
Длинные правые части A -> X1 X2 X3 -> разбить через вспомогательные: A -> X1 Y1, Y1 -> X2 X3; терминалы внутри длинных правил заменить на новые нетерминалы

Почему порядок шагов алгоритма CNF имеет значение?

Нормальная форма Грейбах (GNF)

**GNF (Greibach Normal Form, 1965)** - альтернативная нормальная форма: каждое правило имеет вид `A -> a α`, где `a` - терминал, а `α` - строка нетерминалов (возможно пустая). Первый символ правой части всегда терминал. Это даёт сильное свойство: каждое применение правила немедленно «выплёвывает» один символ ленты.

GNF полезна для построения PDA по грамматике: правило `A -> a B C D` напрямую превращается в переход PDA, читающий `a` со стека и кладущий `B C D`. Полное соответствие grammar - PDA становится прозрачным. Также GNF гарантирует отсутствие левой рекурсии - важно для рекурсивно-нисходящего парсинга.

Что общее у CNF и GNF и в чём различие?

Применение: CYK и теоретический анализ

CNF - входной формат для алгоритма CYK (следующий урок), который проверяет принадлежность строки КС-языку за O(n³ * |G|). Алгоритм заполняет таблицу: на позиции `[i, j]` записывает множество нетерминалов, выводящих подстроку `s[i..j]`. Чистая правая часть `BC` позволяет рассматривать одно правило как пару «левый префикс + правый суффикс».

Pumping lemma для КС-языков (Бар-Хиллел, 1961) формулируется через CNF: длинная строка из языка содержит фрагмент `uvwxy`, где `vwx` короче некоторой константы, а перекачка `uv^i w x^i y` остаётся в языке. Доказательство опирается на дерево вывода в CNF-грамматике с глубиной > log |s|.

Если грамматика в CNF, она всегда даёт более быстрый парсинг

CNF делает возможным алгоритм CYK с O(n³), но любой LL/LR-парсер на исходной грамматике (после устранения левой рекурсии) работает за O(n)

CNF - инструмент теоретического анализа и универсальных алгоритмов парсинга. Промышленные парсеры используют ограниченные подклассы КС-грамматик (LL(k), LR(k)) и работают на них линейно. CNF - не оптимизация, а нормализация

Почему промышленные компиляторы НЕ используют CNF для парсинга, хотя CYK работает на CNF?

CNF универсальна, но цена универсальности - кубическая сложность. Промышленность жертвует выразительностью грамматики ради линейного парсинга.

Ключевые идеи

**CNF** - правила вида `A -> BC` или `A -> a`; стандартный вход для CYK-алгоритма
**GNF** - правило `A -> aα`, первый символ - терминал; удобна для построения PDA и устранения левой рекурсии
**Алгоритм CNF** - четыре шага: новый старт, ε-правила, unit-правила, разбиение длинных - порядок шагов важен
**Применение** - CNF и GNF используются в теории (pumping lemma) и в универсальных парсерах (CYK, Earley); промышленные компиляторы предпочитают LL/LR на исходной грамматике

Связанные темы

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

Автоматы с магазинной памятью (PDA) — GNF напрямую переводится в PDA: правило `A -> aBCD` превращается в переход «читаем a, кладём BCD» - архитектура PDA становится прозрачной
Алгоритм CYK — CYK работает строго на CNF-грамматиках за O(n^3); CNF - предусловие для применения CYK
Контекстно-свободные грамматики — Нормальные формы доказывают, что класс КС-языков не зависит от формы записи - это фундаментальный результат теории

Вопросы для размышления

Если CNF делает грамматику менее читаемой, а парсинг по-прежнему O(n^3), зачем вообще нужна эта форма помимо доказательств теорем?
Может ли существовать «третья» нормальная форма, отличная от CNF и GNF, с какими-то другими полезными свойствами? Какие свойства были бы полезны?
Pumping lemma доказывается через дерево вывода в CNF. Что было бы, если бы доказательство пытались провести напрямую на исходной грамматике с длинными правилами?

Связанные уроки

fl-13-pda — PDA и CFG эквивалентны - нормализация CFG нужна для обоих
fl-15-cyk — CYK работает исключительно на CNF-грамматиках
fl-12-cfg — CFG - базовая структура перед нормализацией
alg-21-dp — CYK на CNF - классическая DP задача на строках
comp-14-parser-generators