The Pumping Lemma: Examples

Lemma: The language $L$ = $\{a^nb^nc^n\; \mid\; n \geq 1\}$ is not context free.
Proof (By contradiction)
Suppose this language is context-free; then it has a context-free grammar.
Let $K$ be the constant associated with this grammar by the Pumping Lemma.
Consider the string $a^Kb^Kc^K$, which is in $L$ and has length greater than $K$.
By the Pumping Lemma this must be representable as $uvxyz$, such that all $uv^ixy^iz$ are also in $L$.
This is impossible, since:

-

either $v$ or $y$ cannot contain a mixture of letters from $\{a,b,c\}$; otherwise they would be in the wrong order for $uv^2xy^2z$

-

if $v$ or $y$ conatin just `a's, `b's or `c's, then $uv^2xy^2z$ cannot maintain the balance between the three letters (it can, of course maintain the balance between two)

${\cal QED}$

Lemma: The language $L$ = $\{a^ib^jc^k\; \mid\; i < j\; and\; i < k\}$ is not context free.
Proof (By contradiction)
Suppose this language is context-free; then it has a context-free grammar.
Let $K$ be the constant associated with this grammar by the Pumping Lemma.
Consider the string $a^Kb^{K+1}c^{K+1}$, which is in $L$ and has length greater than $K$.
By the Pumping Lemma this must be representable as $uvxyz$, such that all $uv^ixy^iz$ are also in $L$.

-

By the same argument as for the previous lemma neither $v$ nor $y$ may contain a mixture of symbols.

-

Suppose $v$ consists entirely of `a's.
Then there is no way $y$, which cannot have both `b's and `c's, can generate enough of these letters to keep their number greater than that of the `a's (it can do it for one or the other of them, not both).
Similarly $y$ cannot consist of just `a's.

-

So suppose then that $v$ or $y$ contains only `b's or only `c's.
Consider the string $uv^0xy^0z$ which must be in $L$. Since we have dropped both $v$ and $y$, we must have at least one `b' or one `c' less than we had in $uvxyz$, which was $a^Kb^{K+1}c^{K+1}$. Consequently, this string no longer has enough of either `b's or `c's to be a member of $L$.

${\cal QED}$