Грамматика (КС) для языка $L=\{a^n{b}^n{c}^m\mid n\ge 0,m\ge 0\}$:
$G=(V,\Sigma ,R,S)$, где
$V=\{S,A,C\}$, $\Sigma =\{a,b,c\}$,
правила $R$:
$$S\to ACA\to aAb\mid \epsilon C\to cC\mid \epsilon$$
Пояснение: нетерминал $A$ порождает равное число $a$ и $b$ (в виде $a^n{b}^n$), а $C$ — произвольное число $c$.
Строка $aabbbc$: это последовательность $a^2{b}^3{c}^1$. Для языка $L$ требуется число $b$ равно числу $a$, то есть строка должна иметь вид $a^n{b}^n{c}^m$. Поскольку здесь $2\ne 3$, строка $aabbbc$ не принадлежит $L$ и потому в грамматике $G$ выводу не подлежит.
Пример корректного вывода строки $aabbc$ (то есть $a^2{b}^2{c}^1$) в данной грамматике:
$$\begin{array}{l}S\Rightarrow AC\\ \Rightarrow (aAb)C\\ \Rightarrow (a(aAb)b)C\\ \Rightarrow aaAbbC\\ \Rightarrow aa\epsilon bbC=aabbC\\ \Rightarrow aabb(cC)=aabbcC\\ \Rightarrow aabbc\epsilon =aabbc\end{array}$$
Почему язык $\{a^n{b}^n{c}^n\mid n\ge 0\}$ не контекстно‑свободен (краткое доказательство через лемму о накачке для КС-языков):
Предположим противное: пусть $L_0=\{a^n{b}^n{c}^n\}$ — КС-язык. По лемме существует константа $p$. Возьмём строку
$$s=a^p{b}^p{c}^p\in L_0.$$ По лемме $s$ представимо как $s=uvwxy$, где $|vwx|\le p$, $|vx|\ge 1$ и для всех $i\ge 0$ строка $u{v}^{i}w{x}^{i}y$ принадлежит $L_0$. Поскольку $|vwx|\le p$, подстрока $vwx$ лежит полностью внутри одной из трёх блоков $a^p$, $b^p$ или $c^p$, либо пересекает границу между двумя соседними блоками. Рассмотрим случаи:
- Если $v$ и $x$ лежат только в блоке $a$ (или только в $b$ или только в $c$), то при $i=0$ количество соответствующей буквы убывает, а двух других — нет, поэтому числа $a,b,c$ в строке становятся разными — противоречие.
- Если $v$ и/или $x$ пересекают границу между $a$ и $b$ (или между $b$ и $c$), то при накачке меняются количества двух типов букв, но не третьего, поэтому снова после некоторого $i$ числа $a,b,c$ не будут равны — противоречие.
Во всех вариантах условие леммы приводит к строкам, не принадлежащим $L_0$, что противоречит предположению. Следовательно, $L_0$ не является контекстно‑свободным.