Examples Using the Pumping Theorem for Context-free Languages

Just as with regular languages, we can use this pumping theorem to show that a language is not context-free. The “rules of the game” are the same as for the pumping theorem for regular languages: we get to choose any qualifying string, but then we must show that there is no possibility of satisfying this pumping theorem. As usual, if a language is “pumpable”, we can draw no conclusions—the language may or may not be context-free.

Example 1

The language $a^nb^nc^n$ is not context-free. If it were, we could partition the string $a^pb^pc^p$ into five substrings, $uvxyz$, such that $uv^ixy^iz$ also has runs of equal size of each letter. Since $|vxy| \leq p$, there are five cases to consider:

1. The variable $vxy$ appears wholly within the initial run of $a$’s. In this case, as $v$ and $y$ are pumped, the number of $a$’s increases while the number of the other letters doesn’t change, failing the pumping theorem.
2. The variable $vxy$ contains both $a$’s and $b$’s. We may assume that $vxy=a^kb^m, m+k\leq p$. In this case, the number of $a$’s and/or $b$’s changes, but the $c$’s do not change, again failing the pumping theorem.
3. The variable $vxy$ appears wholly within the run of $b$'s. In this case, as $v$ and $y$ are pumped, the number of $b$’s increases while the number of the other letters doesn’t change, failing the pumping theorem, as in case 1 above.
4. The variable $vxy$ contains both

...