Коротко: лемма о накачке (pumping lemma) для КС-языков — инструмент для доказательства, что ЯЗЫК не контекстно-свободен. Она не предназначена для доказательства непринадлежности ОДНОЙ конкретной строки (для этого достаточно алгоритмического разбора — CYK/Earley). Ниже — формулировка леммы, пошаговый метод её применения к задаче «L не КС», примеры, где стандартная лемма бывает неэффективна, и альтернативные методы.
1) Лемма о накачке (для CFL)
Для некоторого КС-языка $L$ существует число $p$ такое, что всякая строка $s\in L$ с $|s|\ge p$ раскладывается как
$$s=uvwxy$$ с условиями
$$|vwx|\le p,|vx|\ge 1,$$ и для всех $i\ge 0$ $$u{v}^{i}w{x}^{i}y\in L.$$
2) Как применять лемму (метод доказательства, что язык $L$ не КС)
- Предположите противное: $L$ — контекстно-свободен. Тогда существует $p$.
- Подберите «длинную» специально сконструированную строку $s\in L$ с $|s|\ge p$ (обычно симметричную по зависимостям).
- Рассмотрите произвольное разложение $s=uvwxy$ с вышеуказанными ограничениями (нельзя выбирать разложение — вы должны рассмотреть все возможные).
- Для каждого возможного расположения блоков $v,x$ докажите, что существует $i$ (обычно $i=0$ или $i=2$), при котором $u{v}^{i}w{x}^{i}y\notin L$.
- Получается противоречие с леммой, значит $L$ не КС.
Пример (классический): $L=\{a^n{b}^n{c}^n\mid n\ge 0\}$.
- Берём $s=a^p{b}^p{c}^p$. По ограничению $|vwx|\le p$ блок $vwx$ лежит в пределах не более двух соседних видов букв, поэтому накачка изменит число букв не во всех трёх блоках одновременно — откуда следует, что для некоторого $i$ равенства чисел $a,b,c$ нарушаются, значит $u{v}^{i}w{x}^{i}y\notin L$.
3) Ограничения и случаи, где стандартная лемма не даёт исчерпывающего ответа
- Лемма даёт необходимое, но не достаточное условие: некоторые нелегко описываемые НЕ-КС языки могут «выдерживать» конструкцию накачки (в смысле, для выбранных строк и разложений простая аргументация рушится), и прямое применение леммы оказывается громоздким или неубедительным.
- Лемма иногда не подходит, если зависимости в языке распределены по далеко расположенным позициям и простое «локальное» сокращение/увеличение не нарушает структуру в понятном показать-месте.
- Важное замечание: лемма не предназначена для доказывания, что конкретная строка $x$ не принадлежит CFL $L$. Для конкретной строки принадлежность/непринадлежность решаема алгоритмически (см. ниже).
Конкретный типичный пример «трудного случая»: некоторые языки с несколькими независимыми балансами (двумя парами равенств) — прямой насосный аргумент требует очень аккуратного перебора положений $v,x$, и стандартный подход усложняется. В таких случаях стандартная лемма может не дать чистого доказательства, а более сильные приёмы — да.
4) Сильнее и альтернативы
- Ogden's lemma (Огдена). Укрепление: можно пометить $p$ позиций в строке; гарантируется разложение $s=uvwxy$ с $|vwx|\le p$, причём в $v$ и/или $x$ содержится помеченная позиция. Это часто позволяет доказать не-КСность языков с более сложными распределёнными зависимостями (например, некоторые языки с двумя независимыми копированиями; стандартно применяется для $\{a^n{b}^n{c}^n{d}^n\}$ и других).
- Interchange / pumping variants (разные усовершенствования леммы Бар-Хиллеля и др.) — технические усиления для борьбы с хитрыми разбивками.
- Parikh’s theorem (семилинейность). Для любого КС-языка изображение Париха (векторы кратностей букв) является семилинейным множеством. Если Parikh-образ языка не семилинейный, язык не КС. Пример: язык квадратов в унарном алфавите $L=\{a^{n^2}\}$ не семилинейный ⇒ не КС.
- Замыкания и пересечения с регулярным языком. Часто удобнее взять предполагаемый КС-язык $L$, пересечь с регулярным $R$, получить простой язык $L\cap R$ (например, вида $a^{\ast }{b}^{\ast }{c}^{\ast }$) и применить лемму о накачке к полученному языку. Это стандартный приём для «вычленения» нужной формы строк.
- Деревья вывода и нормальная форма грамматики. Анализ длинны путей в выводном дереве (Chomsky normal form): при большом размере строки дерево содержит повторяющиеся нетерминалы по пути ⇒ можно «накачать». Это формализует доказательство леммы и иногда даёт более детальный аргумент.
- Ограничения PDA (поведение стека). Аргументы о том, что один стек не может отслеживать две независимые счётности, дают интуитивные и формальные доказательства не-КСности (используется для языков с независимыми парами счётчиков).
- Семантические/алгебраические методы. Используют свойства родительских мономорфизмов, алгебры языков, логические описания (MSO): иногда удобнее показать невозможность описания в логике с ограниченной памятью.
- Алгоритмически: для проверки непринадлежности конкретной строки $x$ к известному КС-языку $L$ применяйте парсер (CYK, Earley). Для демонстрации непринадлежности строки это самый прямой путь: если парсер отвергает — $x\notin L$.
5) Практические советы по выбору метода
- Если надо доказать, что ЯЗЫК не КС, сначала попытайтесь стандартным pumping lemma (часто хватает).
- Если pumping ломается из-за распределённых зависимостей — примените Ogden.
- Если структура связана с числовыми свойствами (пары счётчиков, квадраты, факторизация) — смотрите Parikh и семилинейность.
- Для конкретной строки — парсинг (CYK/Earley).
- Используйте пересечение с регулярными языками, чтобы «вытащить» нужную форму строк перед применением леммы.
Если нужно, могу привести развёрнутое пошаговое доказательство конкретного примера (например, доказательство не-КСности $\{a^n{b}^n{c}^n\}$ классическим методом и параллельно показать, как это делается через Ogden/Parikh).