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

КСГ и КСЯ

Контекстно-свободная грамматика G = (V, Σ, R, S): V — нетерминалы, Σ — терминалы, R — правила вида A → α (A∈V, α∈(V∪Σ)*), S — стартовый нетерминал.

Язык L(G) = {w ∈ Σ*: S ⟹* w}.

Пример: Язык {aⁿbⁿ: n≥0}: S → ε | aSb.

Нормальная форма Хомского: A → BC или A → a. Всякая КСГ эквивалентна грамматике в НФХ.

Автоматы с магазинной памятью

МПА = (Q, Σ, Γ, δ, q₀, Z₀, F): добавляется магазин (стек) с алфавитом Γ.

Переходы: δ(q, a, Z) = {(p, γ)}: считываем a, снимаем Z, кладём γ.

Теорема: КСЯ = языки, распознаваемые МПА.

КСЯ замкнуты: объединение, конкатенация, звезда Клини. Не замкнуты: пересечение, дополнение (в общем случае).

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

Тип 0 (без ограничений) → рекурсивно перечислимые языки, машины Тьюринга. Тип 1 (контекстные) → ЛБА (линейно ограниченные автоматы). Тип 2 (контекстно-свободные) → МПА. Тип 3 (регулярные) → ДКА.

Каждый тип строго включается в предыдущий.

Алгоритмические задачи

КСЯ: пустота, конечность, принадлежность (алгоритм CYK O(n³|G|)) — разрешимы. Эквивалентность КСГ — неразрешима. Пересечение двух КСЯ не всегда КСЯ.

Нормальные формы КСГ и алгоритм CYK

Нормальная форма Хомского (НФХ): Каждое правило имеет вид A → BC или A → a. Любая КСГ приводится к НФХ за полиномиальное время. НФХ лежит в основе алгоритма CYK (Кок-Янгер-Касами): разбор за O(n³|G|) методом динамического программирования. Таблица dp[i][j][A] = 1, если нетерминал A порождает подстроку s[i..j].

Нормальная форма Гейбаха: Каждое правило A → aα, где a — терминал, α — строка нетерминалов. Удобна для построения рекурсивного спуска (LL-парсеры). В программировании нормальные формы грамматик — база для компиляторов (Yacc, Bison используют LALR(1) грамматики).

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

Регулярные языки (тип 3) ⊂ Контекстно-свободные (тип 2) ⊂ Контекстно-зависимые (тип 1) ⊂ Рекурсивно перечислимые (тип 0). Включения строгие:

• Тип 3: ДКА / регулярные выражения.
• Тип 2: МП-автоматы / КСГ (грамматики языков программирования).
• Тип 1: Линейно ограниченные ТМ (LBA).
• Тип 0: Произвольные ТМ.

Языки типа 1 всегда разрешимы (LBA решает за экспоненциальное время), тип 0 — рекурсивно перечислимы (не обязательно разрешимы).

Детерминированные КСЯ и парсинг

ДКСГ (детерминированные КСЯ) — подкласс КСЯ, распознаваемых детерминированными МП-автоматами. Строго меньше КСЯ: {aⁿbⁿcⁿ: n≥0} — не КСЯ (доказывается насосной леммой для КСЯ), поэтому это не пример КСЯ, а пример языка вне КСЯ. Пример ДКСГ: {aⁿbⁿ: n≥0}. Пример КСЯ, но не ДКСГ: {ww^R: w ∈ {a,b}*} (палиндромы чётной длины) — ДМПА не может справиться из-за недетерминизма в центре.

Языки программирования: LL(k) и LR(k) грамматики — детерминированные подклассы, для которых существуют эффективные (линейные по длине входа) парсеры. LR(1) грамматики охватывают большинство практических языков.

Лемма о накачке для КСЯ

Лемма о накачке (контекстно-свободные): Для любого КСЯ L существует p, что любая строка w ∈ L длиной ≥ p разбивается w = uvxyz: |vy| ≥ 1, |vxy| ≤ p, uvⁿxyⁿz ∈ L для всех n ≥ 0. Доказательство через дерево разбора: длинная строка → дерево высотой > |G| → повторяющийся нетерминал → «накачать» между двумя вхождениями. Пример применения: {aⁿbⁿcⁿ} не КСЯ.

Атрибутные грамматики

Атрибутная грамматика расширяет КСГ атрибутами для нетерминалов. Синтезированные атрибуты: вычисляются из потомков (снизу вверх). Наследованные атрибуты: передаются от родителя или братьев (сверху вниз). Применяются для семантического анализа в компиляторах: вычисление типов, проверка объявлений переменных. Нотация: S-атрибутные грамматики (только синтезированные) — особенно удобны для LR-парсеров.

Трансдьюсеры и транслирующие автоматы

Конечный преобразователь (transducer): как ДКА, но при переходе выдаёт выходной символ (Moore-машина или Mealy-машина). Меали: выход на переходе; Мур: выход в состоянии. Применение: лексические преобразования, транслитерация, синтез речи. Автоматные морфизмы: для регулярных языков — замыкание под гомоморфизмами, обратными гомоморфизмами и пересечением с регулярными → ещё один способ доказывать нерегулярность.

Сравнительная сложность грамматических классов

КСЯ замкнуты: объединение, конкатенация, звезда Клини, гомоморфизм, обратный гомоморфизм, пересечение с регулярным. Не замкнуты: пересечение, дополнение. КСЯ ∩ КСЯ может быть не КСЯ: классический пример — {aⁿbⁿcᵐ: n,m≥0} ∩ {aᵐbⁿcⁿ: n,m≥0} = {aⁿbⁿcⁿ: n≥0}, а {aⁿbⁿcⁿ} не КСЯ по насосной лемме. Контекстно-зависимые: замкнуты под пересечением и дополнением, но неразрешимы для пустоты. Рекурсивно перечислимые: только пересечение и объединение.

Алгоритм CYK и вероятностные КСГ

CYK (Кока-Янгера-Касами): проверить, принадлежит ли строка w КСЯ за O(n³|G|). Требует нормальную форму Хомского (НФХ): A → BC или A → a. PCFG (вероятностные КСГ): каждое правило A → α имеет вероятность P(α|A). Сумма вероятностей всех правил для A = 1. Наиболее вероятный разбор — алгоритм Витерби на PCFG. Обучение параметров: алгоритм Inside-Outside (аналог Baum-Welch для HMM). Применяется в статистическом синтаксическом анализе текста.

Численный пример: вывод в КСГ и алгоритм CYK

Задача: КСГ G: S→AB, A→a, B→b. Строка w=«ab». Принадлежит ли w L(G)?

Шаг 1: CYK-таблица (нормальная форма Хомского выполнена). Шаги длины 1: w₁=a: dp[1,1]={A}; w₂=b: dp[2,2]={B}.

Шаг 2: Шаг длины 2: dp[1,2]. Проверяем: есть ли правило X→YZ, где Y∈dp[1,1]={A} и Z∈dp[2,2]={B}? S→AB: A∈{A} ✓, B∈{B} ✓. Значит dp[1,2]={S}.

Шаг 3: S∈dp[1,2] → w=«ab»∈L(G). Дерево вывода: S⟹AB⟹aB⟹ab. Проверим w=«ba»: dp[1,1]={B}, dp[2,2]={A}. dp[1,2]: S→AB — A∈{B}? Нет. dp[1,2]={}. S∉dp[1,2] → «ba»∉L(G).

Шаг 4: Сложность CYK: O(n³·|G|). Для предложения из n=20 слов и |G|=50 правил: 20³·50=400 000 операций. PCFG добавляет веса: P(S→AB)=0.7, P(A→a)=1.0, P(B→b)=1.0. Вероятность разбора «ab»: 0.7·1·1=0.70. Алгоритм Витерби на PCFG выбирает наиболее вероятное синтаксическое дерево предложения.