Лемма о накачке для КС-языков

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

Лемма о накачке для КС-языков: для каждого КС-языка есть p такое, что любую строку s длиной ≥ p можно разбить s = uvwxy, где |vx| > 0, |vwx| ≤ p, и uvⁱwxⁱy ∈ L для всех i ≥ 0.

Почему накачиваются два куска

Интуиция снова в повторе, но теперь не состояния, а нетерминала в дереве разбора. Если строка достаточно длинна, дерево разбора высокое, и на каком-то пути от корня нетерминал A повторяется: A порождает поддерево, внутри которого снова A. Это даёт «помпу»: участок между двумя A можно вставлять сколько угодно раз. Но раскрытие A → ...A... порождает символы по обе стороны от внутреннего A — отсюда два накачиваемых куска v (слева) и x (справа), растущих синхронно.

повтор нетерминала A в дереве разбора:

        S
        |
        A   ← внешний A
      / | \
     u  A  y      ← v и y вокруг внутреннего A... 
      / | \       точнее: A ⇒ v A x
     v  A  x
     |  |  |
    ... w ...

накачка: u v^i w x^i y ∈ L  — v и x растут вместе

Доказываем: aⁿbⁿcⁿ не КС

Язык L = {aⁿbⁿcⁿ} (равное число a, b, c) — не контекстно-свободен. От противного: пусть КС, есть p. Берём s = a^pb^pc^p. По лемме s = uvwxy с |vwx| ≤ p и |vx| > 0. Поскольку |vwx| ≤ p, окно vwx не может покрыть все три буквы сразу (между крайними a и крайними c расстояние больше p). Значит vx содержит максимум два вида символов из трёх. Накачаем i=2: какой-то буквы станет больше, а третьей — нет, баланс сломан, строки нет в L. Противоречие — L не КС. Стек справляется с двумя «счётчиками» (a против b), но не с тремя одновременно.

Проверим накачку численно

Покажем, что накачка aⁿbⁿcⁿ выбрасывает строку из языка при любом разумном разбиении.

def is_anbncn(s):
    n = len(s) // 3
    return s == "a"*n + "b"*n + "c"*n and len(s) % 3 == 0

# s = aaabbbccc (n=3). Берём v='a', x='b' (окно vwx внутри a..b, ≤ p).
# i=1 даёт исходную строку (она в языке), i≠1 — ломает баланс.
u, v, w, x, y = "aa", "a", "bb", "b", "ccc"
for i in range(3):
    s = u + v*i + w + x*i + y
    print(f"i={i}: {s:<11} в a^n b^n c^n? {is_anbncn(s)}")

Вывод:

i=0: aabbccc     в a^n b^n c^n? False
i=1: aaabbbccc   в a^n b^n c^n? True
i=2: aaaabbbbccc в a^n b^n c^n? False

При i=1 получаем исходную строку aaabbbccc (она в языке) — это «нулевая» накачка. А вот i=0 и i=2 меняют только число a и b, не трогая c, и баланс трёх букв мгновенно ломается. Накачка двух из трёх букв при неизменной третьей всегда выводит строку из языка.

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

Лемма для КС — следствие того, что в высоком дереве разбора путь длиннее числа нетерминалов, и нетерминал повторяется (снова принцип Дирихле, но по высоте дерева). Условие |vwx| ≤ p ограничивает «ширину» помпы — именно оно не даёт окну захватить все три буквы в aⁿbⁿcⁿ. Как и в регулярном случае, лемма даёт необходимое условие: есть не-КС языки, проходящие лемму, для них нужны более тонкие методы (лемма Огдена).

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

Качать один кусок, как у регулярных. В КС-лемме два синхронных куска v и x; забыть про x — грубая ошибка.

Игнорировать |vwx| ≤ p. Это ключевое ограничение: оно мешает окну охватить все буквы сразу, на нём держится всё доказательство для aⁿbⁿcⁿ.

Думать, что лемма доказывает КС-принадлежность. Нет, только не-КС; прохождение леммы ничего не гарантирует.

Итог

Лемма о накачке для КС: s = uvwxy, накачиваются два участка v и x синхронно (|vx| > 0, |vwx| ≤ p).
Причина — повтор нетерминала в дереве разбора, порождающий символы по обе стороны.
aⁿbⁿcⁿ не КС: окно vwx не покрывает все три буквы, накачка ломает баланс трёх счётчиков.
Лемма — необходимое, но не достаточное условие; для тонких случаев есть лемма Огдена.