Recall warm-up
- CYK complexity?
Stuck? Peek at 3.4.2 Algorithms for CFLs: emptiness, finiteness, membership (CYK)
- Emptiness: is S generating? Finiteness: cycle in the cleaned variable graph. Membership: CYK O(n³|G|), CNF required.
- No algorithm for general CFGs: equivalence, universality, ambiguity, regularity, emptiness of intersection.
- Max yield of a CNF tree whose binary part has height h?
Stuck? Peek at 3.2.2 Chomsky and Greibach normal forms
- CNF: A → BC | a (+ S → ε). Length n ⇒ 2n − 1 steps; n − 1 binary nodes. Height h ⇒ |w| ≤ 2^(h−1).
- Conversion: simplify, replace terminals in long bodies, split long bodies.
- GNF: A → aα. Length n ⇒ n steps. No left recursion.
- Regular pumping lemma conditions?
Stuck? Peek at 2.4.3 Pumping lemma for regular languages
- L regular ⇒ ∃p ∀w ∈ L, |w| ≥ p, ∃ xyz: |xy| ≤ p, |y| ≥ 1, ∀i ≥ 0: xyⁱz ∈ L. p = #states.
- Game: they pick p and split; you pick w and i. Beat every split.
- Standard picks: aᵖbᵖ; a^{p²}; aᵖbaᵖb (ww); prime q ≥ p+2 with i = q+1.
- Necessary, not sufficient. Finite languages pass vacuously.
The Hook
A PDA has one stack: it can match one pair of counts, but not two at once. aⁿbⁿcⁿ needs a’s = b’s and b’s = c’s simultaneously. To prove no PDA can do it, use the pumping lemma for CFLs: every long string of a CFL has two pieces that can be pumped together, close to each other.
Predict First
In a tall parse tree, some path from root to leaf has more variables than the grammar has. What must happen on that path?
Core Concept
Prediction check
A variable repeats on the path (pigeonhole, again). The upper copy of it derives a string containing what the lower copy derives — so the region between them can be repeated or removed.
The lemma
- |vwx| ≤ p,
- |vx| ≥ 1,
- u vⁱ w xⁱ y ∈ L for every i ≥ 0.
v and x are pumped together; the window vwx is short, so it can touch at most two adjacent blocks of something like aⁿbⁿcⁿ.
Why it holds
Take a CNF grammar with k variables, p = 2ᵏ. A string of length ≥ p has a parse tree whose longest path has more than k variables (binary tree height bound, 3.2.2). Among the lowest k + 1 variables on that path, some variable A repeats. The upper A yields vwx (short, because it is low in the tree) and the lower A yields w; v and x are not both empty in CNF.
Classic: aⁿbⁿcⁿ is not a CFL
z = aᵖbᵖcᵖ. Since |vwx| ≤ p, the window touches at most two of the three blocks (never both a’s and c’s). Pumping with i = 2 increases at most two of the counts — the third falls behind ⇒ not in L. Every split loses ⇒ not a CFL.
Classic: ww is not a CFL
z = aᵖbᵖaᵖbᵖ. The window vwx (length ≤ p) lies within one block or across two neighbouring blocks. Pumping down (i = 0) shortens one or two neighbouring blocks, so the two halves no longer match. Not a CFL. (Contrast: wwᴿ is a CFL; and the complement of ww is a CFL.)
Other standard non-CFLs
{ a^{n²} }, { aᵖ : p prime } (unary non-regular sets are never CFLs, since unary CFLs are regular), { aⁱbʲcᵏ : i < j < k }, { w : #a = #b = #c }, { aⁿbᵐcⁿdᵐ } (crossing pairs).
Putting it together
- Long strings of a CFL have two pieces v, x inside a short window that pump together.
- One stack can match one pair of counts, not three-way or crossing ones.
- Unary CFLs are regular; ww and aⁿbⁿcⁿ are not CFLs.
Visual
regular pumping w = x y z |xy| ≤ p one pump near the start CFL pumping z = u v w x y |vwx| ≤ p two pumps, together, anywhere
Worked Examples
What must be non-empty in the CFL pumping lemma?
Show the full solution
vx: at least one of v and x is non-empty (|vx| ≥ 1).
Why can’t the window vwx touch a’s and c’s in aᵖbᵖcᵖ?
Show the full solution
Between the last a and the first c lie p b’s, so any substring touching both has length ≥ p + 2 > p.
Which are not CFLs? (i) { aⁿbⁿcⁿ } (ii) { aⁿbⁿcᵐ : m ≤ n } (iii) { ww } (iv) { aⁿbᵐcⁿdᵐ }
Show the full solution
(i) not CFL. (ii) { aⁿbⁿcᵐ : m ≤ n } needs a = b and c ≤ b simultaneously — not a CFL (pump a window in the b–c region up: the a–b equality or the c ≤ n bound breaks). (iii) not CFL. (iv) not CFL (crossing). All four are non-CFL.
GATE Traps
- CFL pumping: |vwx| ≤ p (the window), not |uv| ≤ p.
- Both v and x are pumped with the same i.
- Passing the lemma proves nothing (like the regular one).
- wwᴿ is a CFL; ww is not. The complement of ww is a CFL.
Memory Hook
Two hands on the same short rope: v and x are pulled together, and the rope (vwx) is too short to reach three blocks.
Connect the Dots
Last lesson of Phase 3: put everything together and classify languages fast — regular, DCFL, CFL, or not CFL — the GATE favourite.
Self-Test
- MCQ
In the CFL pumping lemma, which condition is correct?
- |uv| ≤ p
- |vwx| ≤ p
- |w| ≥ 1
- |uvw| ≤ p
- MSQ
Which are not context-free?
- { aⁿbⁿcⁿ }
- { wwᴿ }
- { ww }
- { aⁿbᵐcⁿdᵐ }
- MCQ
The pumping length for a CNF grammar with k variables can be taken as:
- k
- 2k
- 2ᵏ
- k²
- MCQ
Every unary CFL is:
- regular
- not regular
- finite
- inherently ambiguous
Rule Card
- L CFL ⇒ ∃p ∀z ∈ L, |z| ≥ p: z = uvwxy, |vwx| ≤ p, |vx| ≥ 1, uvⁱwxⁱy ∈ L ∀i ≥ 0. p = 2ᵏ (CNF, k variables).
- Non-CFL: aⁿbⁿcⁿ, ww, aⁿbᵐcⁿdᵐ, #a=#b=#c, a^{n²}, a^{prime}, aⁱbʲcᵏ (i<j<k).
- Unary CFL ⇒ regular. Complement of ww is a CFL.
Concept Ledger
- pumping lemma (CFL)
- window vwx
- repeated variable on a parse-tree path
- standard non-CFLs
Answer Vault
Reveal answers when you’re ready
Warm-up answers
- O(n³ · |G|).
- 2ʰ.
- |xy| ≤ p, |y| ≥ 1, xyⁱz ∈ L for all i.
Self-test answers
- B — The window.
- A: That resembles the regular lemma.
- C: w may be empty.
- D: Wrong.
- ACD — Standard non-CFLs.
- B: Palindromes are CFL.
- C — Tree height argument.
- A: Too small.
- B: Too small.
- D: Not the standard bound.
- A — Hence a^{prime} and a^{n²} are not CFLs.
- B: Opposite.
- C: a* is infinite.
- D: No.
Flashcards
- CFL pumping lemma conditions?
Reveal answer
|vwx| ≤ p, |vx| ≥ 1, uvⁱwxⁱy ∈ L for all i ≥ 0. - Is ww context-free? wwᴿ?
Reveal answer
ww: no. wwᴿ: yes. - Are unary CFLs regular?
Reveal answer
Yes. - Is the complement of { ww } a CFL?
Reveal answer
Yes.