Коротко: язык L = { a^n b^n c^n | n ≥ 0 } не является контекстно‑свободным. Ниже — стандартное доказательство с помощью леммы о накачке для КС‑языков, затем — какие автоматы его распознают и какие практические следствия для построения парсеров.

1) Лемма о накачке для контекстно‑свободных языков $Bar‑Hillel$ Существует число p $постоянноедляданногоязыка$ такое, что для любого слова s ∈ L с |s| ≥ p существует разбиение s = u v w x y, удовлетворяющее

|v w x| ≤ p,|v x| > 0,
и для всех i ≥ 0 слово u v^i w x^i y ∈ L.

2) Доказательство, что L не контекстно‑свободен
Предположим противное: L — КС‑язык, и пусть p — число из леммы. Возьмём s = a^p b^p c^p $|s|=3p\ge p$. По лемме s = u v w x y, |v w x| ≤ p и |v x| > 0.

Так как длина фрагмента vwx ≤ p, этот фрагмент полностью лежит не более чем в двух соседних блоках символов: он не может одновременно содержать символы a, b и c. Иначе его длина была бы > p $посколькукаждыйблокa^p,b^p,c^pимеетдлинуp,аvwxограниченp$. Значит возможны пять случаев:

vwx находится полностью в блоке a^p;полностью в блоке b^p;полностью в блоке c^p;пересекает границу a^p и b^p $т.е.содержиттолькоaиb$;пересекает границу b^p и c^p $т.е.содержиттолькоbиc$.

Во всех случаях v и x состоят только из одного или двух типов символов, но не из всех трёх. По лемме для любого i у слова u v^i w x^i y должны быть равные количества a, b и c. Возьмём i = 0 $удалимvиx$. Тогда число символов одного типа $илидвухтипов$ уменьшится, а число третьего типа останется прежним, поэтому соотношение a:b:c нарушится. Формально:

Если v и x содержат только a $илитолькоb,илитолькоc$, то при i = 0 уменьшится ровно число соответствующих символов, а два других остаются равными p, значит числа станут неравными.Если v и x содержат a и b $границаa|b$, то при i = 0 уменьшатся числа и a, и b на одно и то же положительное значение, число c останется p — тогда a и b станут < p $возможноравнымеждусобой$, но c = p, так что все три не равны.Аналогично для случая b и c.

Во всех вариантах u v^0 w x^0 y ∉ L, что противоречит лемме. Следовательно, L не является контекстно‑свободным.

$Усиление:аналогичныйвыводможнодатьспомощьюлеммыОгдена—онамощнееидаёттежерезультаты.$

3) Класс автоматов, распознающий L

L не распознаёт ни детерминированный, ни недетерминированный одно‑стековый pushdown‑автомат $PDA$ — это и есть факт «не КС‑язык».L распознаётся более мощными устройствами:
PDA с двумя стеками $илиодинPDA,укоторогоестьдванезависимыхстека$. Два стека эквивалентны машине Тьюринга по вычислительной мощности, поэтому с их помощью можно легко проверить a^n b^n c^n $например:впервыйстекпушимa,причтенииbпоп‑аемизпервогоипушимввторой;причтенииcпоп‑аемизвторого—проверяемпустоту$.Линейно ограниченная машина $LBA,т.е.машинаТьюрингаспамятью,ограниченнойвходнойдлиной$ — язык контекстно‑чувствительный $тип‑1виерархииХомского$. Для a^n b^n c^n существует детерминированный алгоритм LBA, который последовательно «маркирует» соответствующие тройки символов, проходя по ленте несколько раз.Формальные грамматики более высокого уровня $например,indexed‑грамматикиАхо,TAGидр.$ могут генерировать такие языки.

4) Практические последствия для парсеростроения

Большинство синтаксических анализаторов $LL,LR,GLRипрочие$, используемых в компиляторах и инструментах, ориентированы на контекстно‑свободные грамматики. Они не могут выразить и распознать языки с «трёхсторонними» равенствами типа a^n b^n c^n чисто синтаксически.В практических языках такие строгие «счётные» зависимости встречаются редко на уровне чистого синтаксиса; если нужны комплексные семантические связи $например,одинаковоеколичествочего‑товтрёхместах$, их обычно проверяют в семантической фазе $semanticanalysis$ с использованием дополнительных структур данных $счётчики,таблицысимволов$ или в отдельных проходах.Если действительно требуется проверка вида a^n b^n c^n, есть практичные подходы:
оставить синтаксис КС и добавить семантические действия в парсер $встроенныесчётчики/стэкивдействиеприсворачивании/развёртывании$;сделать несколько проходов: синтаксический парсер распознаёт общую форму, затем отдельный алгоритм проверяет равенство чисел;использовать расширенные формализмы $indexed‑грамматики,контекстно‑чувствительныеграмматики$ или машину с двумя стеками, если это оправдано.Вывод для разработчика парсеров: если требование выразимо только в языке выше контекстно‑свободного уровня, не пытайтесь «заставить» CFG это сделать — лучше отделить синтаксис и семантику или расширить механизм парсера семантическими действиями/проверками.

Краткое резюме: L = { a^n b^n c^n } не КС — классический пример языка, доказываемого леммой о накачке; для распознавания нужны более мощные машины $двестеки,LBAит.д.$; в практике парсеростроения такие зависимости обычно проверяют семантически, а не чисто синтаксически.