--- title: "Pumping lemma (CFL): ww not CF" subject: "Theory of Computation" chapter: 3 key: "semester_3/theory_of_computation:pumping-cfl-ww" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pumping-cfl-ww site: BCT Engineering --- # Pumping lemma (CFL): ww not CF Theory of Computation · Chapter 3: Context Free Grammar - Asked in: 2074 Asoj - Video: [Pumping Lemma (For Context Free Languages)](https://www.youtube.com/watch?v=jRhqx1_KcCk) — Neso Academy - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/pumping-cfl-ww - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3 ## Question Define the pumping lemma for context free languages. Prove that L = {ww | w ∈ {0,1}*} is not context free. ## Short answer Pumping lemma: for a CFL L, there exists p such that every s in L with |s|≥p can be split uvxyz, |vxy|≤p, |vy|≥1, uv^i xy^i z in L. For {ww}, intersect with 0*1*0*1* to get {0^i1^j0^i1^j}; choose s=0^p1^p0^p1^p. With |vxy|≤p, vxy hits at most two blocks, so pumping breaks block equality, contradiction. ## Answer #### 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 ∩ 0*1*0*1* = { 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 0*1*0*1* 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.) ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Why is L intersected with 0*1*0*1* in the proof? A. To reduce L to 0ⁱ1ʲ0ⁱ1ʲ using that CFL ∩ regular is a CFL B. To make L finite C. To remove the 1s D. To make the language regular Answer: A. If L were a CFL, then L ∩ 0*1*0*1* would be a CFL, and it has a simpler form. (Key point: Regular intersection trick) 2. Which string is pumped? A. 0ᵖ1ᵖ B. 0ᵖ1ᵖ0ᵖ1ᵖ C. (01)ᵖ D. 0ᵖ0ᵖ Answer: B. s = 0ᵖ1ᵖ0ᵖ1ᵖ is in L′ and has four blocks of length p. (Key point: Choice of string) 3. Since |vxy| ≤ p, vxy touches: A. At most two adjacent blocks B. All four blocks C. Only B1 D. No block Answer: A. Each block has length p, so vxy spans at most two adjacent blocks. (Key point: Blocks touched) 4. Why is uv²xy²z not in L′? A. It has a different alphabet B. Pumping changes a block length, breaking |B1| = |B3| or |B2| = |B4|, or the shape C. It becomes empty D. Pumping removes all 0s Answer: B. Membership needs matching halves, and pumping upsets at least one of the equalities. (Key point: Contradiction) ## Related in Theory of Computation - [Pumping lemma (CFL): aⁿbⁿcⁿ not CF](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-cfl-an-bn-cn) — Theory of Computation, chapter 3 - [Pumping lemma: a^(n²) not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-square-not-regular) — Theory of Computation, chapter 2, asked 5× - [Pumping lemma: aⁿb²ⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-an-b2n-not-regular) — Theory of Computation, chapter 2, asked 3× - [Pumping lemma: aⁿbaⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-anban-not-regular) — Theory of Computation, chapter 2 - [CFGs for L1, L2; L1∩L2 not CF](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-l1-l2-pumping-proof) — Theory of Computation, chapter 3 - [Pumping lemma: equal 0s and 1s](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-equal-zeros-ones) — Theory of Computation, chapter 2, asked 2×