3.4CFL closure and the pumping lemma
The idea
CFLs are closed under union, concatenation, star and reversal, but not under intersection or complement. The pumping lemma for CFLs shows some languages are not context-free.
Think of it like this: A stack can match one pair of things; ask it to match two pairs and it runs out of tricks.
Why it exists
Closure questions and "is it a CFL?" classification are the most repeated TOC items.
How it works
- Union, concatenation, star, reversal, homomorphism: closed.
- Intersection and complement: not closed, but CFL ∩ regular is a CFL.
- Pumping: s = uvwxy, |vwx| ≤ p, |vx| ≥ 1, uvⁱwxⁱy ∈ L.
- aⁿbⁿcⁿ, ww, and {aⁿ²} fail the CFL pumping lemma.
Worked example: aⁿbⁿ ∩ ... gives aⁿbⁿcⁿ
{aⁿbⁿcᵐ} and {aᵐbⁿcⁿ} are CFLs, but their intersection {aⁿbⁿcⁿ} is not: CFLs are not closed under intersection.
Now play with it
- →Study the closure table, then classify the languages in the quiz.
| Operation | Regular | DCFL | CFL | CSL | Recursive | RE |
|---|---|---|---|---|---|---|
| Union | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Intersection | ✓ | ✗ | ✗ | ✓ | ✓ | ✓ |
| Complement | ✓ | ✓ | ✗ | ✓ | ✓ | ✗ |
| Concatenation | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Kleene star | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Reversal | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Difference | ✓ | ✗ | ✗ | ✓ | ✓ | ✗ |
| ∩ with a regular language | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| Homomorphism | ✓ | ✗ | ✓ | ✗ | ✗ | ✓ |
| Inverse homomorphism | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
Learn the exceptions: CFL has no ∩ and no complement; DCFL has complement but almost nothing else; RE has no complement; CSL and recursive have complement.
Is the language context-free? · question 1 of 7
{ aⁿbⁿcⁿ : n ≥ 0 }
Check yourself
Which operation can take two CFLs to a non-CFL?
Exam notes (the dense version)
CFLs are closed under union, concatenation, star, reversal, homomorphism and intersection with a regular language. They are not closed under intersection or complement. Pumping lemma: s = uvwxy with |vwx| ≤ p, |vx| ≥ 1, uvⁱwxⁱy ∈ L. Proves aⁿbⁿcⁿ, ww and aⁿ² are not CFLs.
Previous year questions: Context-Free Grammars & Languages (13)
PYQs are grouped by topic, so this is the full set for Context-Free Grammars & Languages; try the ones that match this subtopic. Open all 13 on the topic page.