The Pumping Lemma for CFLs: Statement and Structure

1. From Loops in Automata to Recursion in Grammars

Recall the Pumping Lemma for Regular Languages. Its logic was rooted in the finite nature of a DFA. A sufficiently long string forces the DFA to revisit a state, creating a "loop" in its state diagram. This loop corresponds to a substring (y in xyz) that can be repeated or removed.

However, this logic won't work for CFLs. A PDA can handle languages like $\{a^n{b}^n\}$ precisely because its stack provides unbounded memory, overcoming the finite-state limitation. The "memory" of a CFL isn't in states, but in the recursive structure of its grammar. Therefore, the Pumping Lemma for CFLs is based not on loops in an automaton, but on repetition within a parse tree.

2. The Core Idea: Tall Parse Trees and Repeated Variables

The proof of the Pumping Lemma for CFLs relies on a key insight from grammars in Chomsky Normal Form (CNF). As you'll remember, any CFL can be generated by a CFG in CNF, where production rules are of the form A → BC or A → a. This results in parse trees that are essentially binary trees.

Here's the chain of logic:

1. Let's say our grammar has k variables.
2. If we generate a very long string, its parse tree must be very "tall".
3. If the tree is tall enough (specifically, if the longest path from the root to a leaf has more than k variables), the Pigeonhole Principle dictates that at least one variable must appear more than once on that path. Let's call this repeated variable A.

This repetition means the grammar has a recursive way of defining A. One instance of A derives another instance of A further down the tree. This structure is what we will exploit for "pumping".

The following image provides a visual schematic of this idea.

3. Decomposing the String and "Pumping"

The repeated variable A allows us to break the string w into five pieces, which we'll call u, v, x, y, z.

• w = uvxyz

As the diagram above shows:

• The top-level derivation generates u, the upper A, and z. So, S ⇒* uAz.
• The upper A recursively generates v, the lower A, and y. So, A ⇒* vAy.
• The lower A eventually generates the terminal string x. So, A ⇒* x.

Because of the recursive rule A ⇒* vAy, we can "pump" it.

• Pumping up (i > 1): We can apply the rule A ⇒* vAy multiple times before finally applying A ⇒* x. This generates strings of the form uv^2xy^2z, uv^3xy^3z, and so on.
• Pumping down (i = 0): We can skip the A ⇒* vAy rule entirely. In the derivation S ⇒* uAz, we can directly substitute the derivation for the smaller part, A ⇒* x, yielding the string uxz.

This logic is the heart of the lemma. The following video provides a detailed walkthrough of this derivation.

4. The Formal Statement of the Pumping Lemma

Now that we have the intuition, we can state the lemma formally. It establishes a property that all context-free languages must satisfy.

Theorem (Pumping Lemma for Context-Free Languages):

If L is a context-free language, then there exists a number p (the pumping length) such that for any string w in L with |w| ≥ p, w can be divided into five substrings, w = uvxyz, satisfying the following three conditions:

1. For all i ≥ 0, the string uv^i x y^i z is in L.
   This is the "pumping" property itself. It states that we can repeat the v and y sections any number of times (including zero), and the resulting string will still be in the language.

2. |vy| > 0 (or equivalently, |v| + |y| > 0).
   This means that the parts being pumped are not both empty. If both v and y were the empty string ε, the pumping action would do nothing, making the lemma trivial and useless. This condition ensures we are pumping a non-empty substring.

3. |vxy| ≤ p.
   This condition constrains the location of the pumpable parts. It says that the substring vxy (the part derived from the upper A in our parse tree) is not arbitrarily long; its length is at most the pumping length p. This means v, x, and y must be relatively close to each other within the string w.

5. Why These Conditions? A Deeper Look

Let's briefly revisit why conditions 2 and 3 must hold, as this deepens the understanding of the lemma's structure.

• Why is |vy| > 0? (Condition 2)
  This follows from the properties of Chomsky Normal Form. The proof relies on a grammar in CNF where ε-productions are eliminated (except possibly for S → ε). When the upper A derives vAy, A ⇒* vAy, the productions used cannot be only unit productions or ε-productions. This forces at least one of v or y to contain terminals. If both were empty, the two occurrences of A in the parse tree would be the same node, which contradicts our premise of finding a repeated variable along a path.

• Why is |vxy| ≤ p? (Condition 3)
  The pumping length p is related to the number of variables k in the grammar (e.g., p = 2^k). The proof of the lemma is constructed by choosing the lowest pair of repeated variables on the longest path in the parse tree. By doing this, we can guarantee that the subtree rooted at the upper A has a height no greater than k+1. A binary tree of a bounded height can only generate a string of a bounded length. This ensures that the yield of that subtree, vxy, has a length at most p. This condition is crucial because it limits the number of ways a string can be split when we later use the lemma.

You can review these points in the following optional video segments.

Conclusion

In this lesson, we have introduced the Pumping Lemma for Context-Free Languages, a fundamental tool for exploring the limits of this language class.

Key Takeaways:

• The Pumping Lemma for CFLs provides a property that every context-free language must have.
• Its logical foundation is the Pigeonhole Principle applied to parse trees: a sufficiently long string implies a tall parse tree, which must contain a repeated variable along some path.
• This repeated variable allows any sufficiently long string w to be decomposed into five parts, w = uvxyz.
• This decomposition must satisfy three critical conditions:
  1. Pumping: uv^ixy^iz is in the language for all i ≥ 0.
  2. Non-empty: At least one of the pumped parts, v or y, must be non-empty (|vy| > 0).
  3. Length Constraint: The core pumpable segment vxy must be no longer than the pumping length p (|vxy| ≤ p).

Preview of the Next Lesson:
Understanding the statement of the lemma is the first step. The real power comes from using it. In our next lesson, we will learn how to apply the Pumping Lemma in a formal proof by contradiction to demonstrate that a given language is not context-free. We will finally be able to prove formally why languages like $\{a^n{b}^n{c}^n\}$ cannot be generated by any CFG.