Pumping lemma (CFL): ww not CF

Pumping lemma for context free languages

If L is a context free language, there is an integer p ≥ 1 (the pumping length) such that every string s ∈ L with |s| ≥ p can be split as s = uvxyz where

1. |vxy| ≤ p,
2. |vy| ≥ 1 (v and y are not both empty),
3. uvⁱxyⁱz ∈ L for every i ≥ 0.

It is used to prove that a language is not context free.

Proof that L = { ww : w ∈ {0,1}* } is not context free

Assume L is context free. We use the closure of CFLs under intersection with a regular language: CFL ∩ regular is context free. So if L is a CFL then

L′ = L ∩ 0101 = { 0ⁱ1ʲ0ⁱ1ʲ : i, j ≥ 0 }

is also a CFL. (A string 0^a1^b0^c1^d is of the form ww exactly when a = c and b = d.) We show L′ is not context free; let p be its pumping length.

Pick s = 0ᵖ1ᵖ0ᵖ1ᵖ ∈ L′, and split it as uvxyz by the lemma. Think of s as four blocks of length p: B1 = 0ᵖ, B2 = 1ᵖ, B3 = 0ᵖ, B4 = 1ᵖ.

• Since |vxy| ≤ p, the part vxy touches at most two adjacent blocks.
• If v or y contains two different symbols (for example "01"), then uv²xy²z has more than four alternating blocks, so it is not in 0101 and hence not in L′. Contradiction.
• Otherwise v and y lie inside single blocks. Pumping with i = 2 changes the length of at least one block touched, because |vy| ≥ 1. But a string of this shape is in L′ only when |B1| = |B3| and |B2| = |B4|.
  • If vxy lies in B1, B2 or both: the length of B1 or B2 changes while B3 and B4 stay p, so |B1| ≠ |B3| or |B2| ≠ |B4|.
  • If vxy lies in B2 and B3: B2 or B3 changes, breaking |B2| = |B4| or |B1| = |B3|.
  • If vxy lies in B3 and B4: B3 or B4 changes, breaking an equality with the unchanged B1 or B2.
  • If vxy lies inside one block, the same holds.

In all cases uv²xy²z ∉ L′, contradicting the lemma. So L′ is not context free, therefore L = { ww } is not context free.

(By contrast, the complement of L is context free, and L is context sensitive.)