Pumping Lemma for Context-Free Languages

Pumping Lemma for CFLs (Statement)

For every context-free language A, there exists a pumping length p such that any string z in A with |z| ≥ p can be split into z = uvwxy where:

1. |vx| > 0 (not both empty)

2. |vwx| ≤ p (middle part is within p symbols)

3. For all i ≥ 0, uvⁱwxⁱy ∈ A.

PL for CFLs: Condition 1 (vx ≠ ε)

Condition 1 (|vx| > 0) means the parts v and x cannot both be empty. At least one of the two pumpable substrings must contain some symbols.

PL for CFLs: Condition 2 (|vwx| ≤ p)

Condition 2 (|vwx| ≤ p) means the middle section (vwx) lies entirely within some p-symbol-long substring of z. It restricts where the repeating pattern can be.

PL for CFLs: Condition 3 (uvⁱwxⁱy ∈ A)

Condition 3 says that simultaneously pumping v and x (repeating them i times) must produce strings that are still in the language A. You pump two parts in tandem.

Using PL to Prove Non-Context-Free

To prove a language L is not context-free, use the contrapositive. Show that for every pumping length p, you can find some string z in L (|z|≥p) that cannot be split to satisfy all three pumping conditions.

The "Demon Game" for CFLs

A strategy game to prove non-context-freeness:

1. Demon picks p.
2. You pick a string z in L, |z| ≥ p.
3. Demon splits z = uvwxy (with |vx|>0, |vwx|≤p).
4. You pick an i ≥ 0.
   You win (L is not a CFL) if uvⁱwxⁱy is not in L. You need a winning strategy for all demon moves.

Why CNF is Used in the Proof

The proof of the Pumping Lemma assumes the grammar is in Chomsky Normal Form (CNF). This guarantees that a parse tree for a long string has a long path where some variable must repeat, creating the v and x pumpable parts.

Pumping Length Choice (k = 2^(m+1))

In the proof, if the CNF grammar has m variables, the pumping length is set to p = 2^(m+1). A string of this length forces a parse tree deep enough for a variable to repeat on a path.

Example: Proving {aⁿbⁿcⁿ} is not a CFL (Step 1&2)

To prove L = {aⁿbⁿcⁿ | n ≥ 0} is not a CFL:

1. Demon picks p.
2. You pick z = aᵖbᵖcᵖ. (Clearly in L, |z| ≥ p).

Example: Proving {aⁿbⁿcⁿ} (Step 3 Analysis)

3. Demon splits z = uvwxy with |vwx| ≤ p and |vx| > 0. Because |vwx| ≤ p, this middle part cannot contain all three symbols a, b, c simultaneously. It can be:
   • Only as
   • Only bs
   • Only cs
   • as and bs
   • bs and cs
     (It cannot be as and cs because they are separated by bs).

Example: Proving {aⁿbⁿcⁿ} (Step 4 & Win)

4. You pick i=2. Pumping v and x disrupts the equal count:
   • If vx is only as, bs, or cs → that symbol's count increases, breaking the aⁿbⁿcⁿ pattern.
   • If vx contains two symbols (e.g., as and bs) → the order a*b*c* is broken or counts become unequal.
     In all cases, uv²wx²y ∉ L. Therefore, L is not a CFL.

Key Difference from Regular PL

The CFL Pumping Lemma is more complex: you split into 5 parts (uvwxy), pump two parts (v and x) in tandem, and the middle part (vwx) is length-limited. The Regular PL splits into 3 parts (xyz) and pumps just one (y).

PL is a Necessary, Not Sufficient Condition

The Pumping Lemma is a necessary condition for a language to be a CFL. If a language is a CFL, it must be pumpable. However, some non-CFLs might also be pumpable. It is used to prove non-context-freeness, not context-freeness.