Доказательство не-КС с помощью леммы о накачке для КС-языков.
Лемма: для любого бесконтекстного языка существует число $p$ такое, что любое слово $s$ с $|s|\ge p$ можно представить как $s=uvwxy$, где $|vwx|\le p$, $|vx|\ge 1$, и для всех $i\ge 0$ слово $u{v}^{i}w{x}^{i}y$ принадлежит языку.
Пусть для противоречия язык $L=\{a^n{b}^n{c}^n\mid n\ge 1\}$ бесконтекстен. Возьмём $p$ из леммы и рассмотрим
$$s=a^p{b}^p{c}^p.$$ По лемме $s=uvwxy$ с $|vwx|\le p$ и $|vx|\ge 1$. Так как длина блока $vwx\le p$, эта подстрока целиком лежит не более чем в двух подряд идущих видах символов: либо внутри одних $a$, либо внутри одних $b$, либо внутри одних $c$, либо пересекает границу $a/b$ или $b/c$. Значит $v$ и $x$ затрагивают не все три типа символов одновременно.
Рассмотрим случаи (всегда можно взять $i=0$ или $i=2$ для контрпримера):
- Если $v$ и $x$ содержат только $a$-символы, то при $i=0$ число $a$ уменьшится, а числа $b,c$ останутся равными $p$: получим слово, где числа букв не все равны, следовательно не в $L$.
- Аналогично, если $v,x$ только из $b$ или только из $c$, то при $i=0$ (или $i=2$) нарушится равенство трёх счётчиков.
- Если $v,x$ пересекают границу $a/b$, то их удаление/добавление изменит числа $a$ и $b$ (вместе), но не число $c$; при некотором $i$ числа трех типов не будут все равны.
- Аналогично для границы $b/c$.
Во всех случаях существует $i$ такое, что $u{v}^{i}w{x}^{i}y\notin L$, что противоречит лемме. Следовательно $L$ не является бесконтекстным.
Формализм, порождающий / распознающий этот язык.
1) Контекстно-чувствительная грамматика (тип-1). Пример Грамматики, порождающей $L$:
$$\begin{array}{rl}S& \to aSBC\mid abc,\\ CB& \to BC,\\ aB& \to ab,\\ bB& \to bb,\\ bC& \to bc,\\ cC& \to cc.\end{array}$$ Идея: многократно применять $S\to aSBC$, затем $S\to abc$, после чего переставлять и заменять $B,C$ на $b,c$, получая $a^n{b}^n{c}^n$. Все правила не укорачивают слово, поэтому грамматика контекстно-чувствительная.
2) Линейно-ограниченный автомат (LBA). НЕЛБА (недетерминированный LBA) или даже детерминированный LBA может распознать $L$ таким образом: на ленте записано входное слово; итеративно помечать (заменять) первый непомеченный $a$ на метку $X$, затем найдя первую непомеченную $b$ пометить её $Y$, затем первую непомеченную $c$ пометить $Z$; повторять, пока не пометятся все символы; в конце проверить, что были только $a$, затем $b$, затем $c$ и что ни один символ не остался непомеченным. Поскольку LBA использует только ограниченную входной длиной память, это распознавание укладывается в модель линейно-ограниченного автомата.