CS 254: Automata and Computability

A sample pumping lemma argument

The following statement and proof illustrate a formal structure that can be used to make an argument based on the pumping lemma for context-free languages.

The statement and proof

Let A = {an bn cn | n ≥ 0}. Then A is not a context-free language.

Proof:

Let k by an arbitrary non-negative integer. Set z = ak bk ck. Then |z| ≥ k.

Let u, v, w, x, and y be any strings for which z = uvwxy, vx ≠ ε, and |vwx| ≤ k. The structure of v, w, and x breaks down into the following cases:

1. vx = ai bj for some i, j ≥ 0 such that i + j > 0. In this case, uv2wx2y will consist of (2k + i + j) a's and b's, followed by k c's. Since the number of a's and b's is strictly greater than twice the number of c's, uv2wx2y ∉ A.
2. vx = bi cj for some i, j ≥ 0 such that i + j > 0. In this case, uv2wx2y will consist of k a's followed by (2k + i + j) b's and c's. Since the number of b's and c's is strictly greater than twice the number of a's, uv2wx2y ∉ A.

There are no more cases than cases 1 and 2 since |vwx| ≤ k. Thus, for any decomposition of z into uvwxy with the properties listed above, there exists an i ≥ 0 (specifically, i = 2) such that uviwxiy ∉ A. Therefore, by the Pumping Lemma, A is not context-free.

Notes on the proof

• The creative part of doing a Pumping Lemma proof is in the selection of z. In the proof above, we define z as we do to prevent vwx from overlapping all three letter sections (a's, b's and c's). By preventing this, we can make a simple letter-counting argument uv2wx2y ∉ A.
• Once we have selected z, we have to demonstrate that for any decomposition z = uvwxy with the length limitations on vwx and vx, we can find a pumped value that fails to be in A. This often descends into a case argument.

• To make a PL proof persuasive and readable, your best bet is to follow the rigid structure as above.

  • Suppose k ≥ 0.
  • Define z = whatever, and make sure it's clear that |z| ≥ k.
  • Suppose z = uvwxy with vx ≠ ε and |vwx| ≤ k.
  • Show that uviwxiy ∉ A for some convenient i. This is often a case-based step (and i may vary from case to case if that makes things easier for you). This is always the longest step in the proof.
  • Sum things up by saying "by the Pumping Lemma, A is not context-free."
• In this proof sample, I have used the smallest number of cases that I could come up with to cover all the possible vwx's. However, these cases are slightly odd in that they overlap. (Just-b's will fall into either case.) Usually, we break things into non-overlapping cases. Here, for example, we could have a case for vwx = all a's, one for all-b's, one for all-c's, one for some a's and some b's, and one for some b's and some c's.