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 $b$’s and $c$’s. As in case 2, the number of $b$’s and/or $c$’s changes, but the $a$’s do not change, again failing the pumping theorem as in case 2 above.
5. The variable $vxy$ appears wholly within the run of $c$'s. In this case, as in cases 1 and 3 above, as $v$ and $v$ are pumped, the number of $c$’s increases while the number of the other letters doesn’t change, failing the pumping theorem.

---

Example 2

The language of two equal halves, $ww$, is not context-free. Consider the string $a^pb^pa^pb^p$. Once again, since $vxy\leq p$, it is not possible for the various parts of the string to pump while keeping the halves of the string equal. There are seven cases to consider:

1. The variable $vxy$ appears within the initial run of $a$’s. In this case, as $v$ and $y$ are pumped, the number of initial $a$’s increases while the number of $a$’s in the third run doesn’t change, failing the pumping theorem.
2. The variable $vxy$ contains both $a$’s and $b$’s from the first two runs. We can assume that $vxy=a^kb^m, m+k\leq p$. In this case, the number of $a$’s and/or $b$’s in the first half changes, but the two trailing runs of letters do not, again failing the pumping theorem.
3. The variable $vxy$ appears only within the first run of $b$'s. In this case, the number of initial $b$’s changes but the second run of $b$’s does not, similar to case 1 above.
4. The variable $vxy$ contains $b$’s followed by $a$’s, failing in the same manner as case 2.
5. The variable $vxy$ is contained in the second run of $a$’s, which is analogous to cases 1 and 3.
6. The variable $vxy$ contains $a$’s and $b$’s from the second half of the string, failing in the same way as cases 2 and 4.
7. The variable $vxy$ is in the last run of $b$’s, failing the same way as cases 1, 3, and 5.

---

Example 3

The language $a^{n^2}, \Sigma=\{a\}$ is not context-free. Consider the string $s=a^{p^2}=uvxyz$. Since $|vxy|\leq p$, we know that $|vy|\leq p$. We will show that pumping up once to $uv^2xy^2z$ does not reach the next square, $a^{(p+1)^2}$.

The difference between the two strings of square lengths is $(p+1)^2-p^2=2p+1$. However, the difference from pumping up once is: