Context-Free Grammars, Push-Down Automata and the Pumping Lemmas
A finite automaton has a fixed amount of memory; a push-down automaton adds one stack, and everything in this chapter follows from what a single stack can and cannot do. It can match one pair of things: a stack is exactly what you need to push n a's and pop them against n b's, which is why {aⁿbⁿ} is context free while being non-regular. It cannot match two pairs at once, because checking the a's against the b's empties the stack and there is nothing left to check the c's with — which is why {aⁿbⁿcⁿ} is not context free. That single sentence about one stack predicts most of the answers in this topic, including the closure properties. The important one, and the one most questions turn on, is an asymmetry with the regular languages: regular languages are closed under intersection and complement, and context-free languages are closed under neither. The witness is worth knowing rather than deriving under time pressure. L₁ = {aⁿbⁿcᵐ} is context free — match a against b, ignore c. L₂ = {aᵐbⁿcⁿ} is context free — ignore a, match b against c. Their intersection forces all three counts equal, giving {aⁿbⁿcⁿ}, which is not context free. So two CFLs intersect to a non-CFL, and since closure under complement plus closure under union would give closure under intersection by De Morgan, CFLs cannot be closed under complement either. The pumping lemmas are the tools for proving these negatives, and both have the same logical shape worth being precise about: they can refute membership of a class and can never confirm it.
The Closure Asymmetry, With Its Witness
| Operation | Regular | Context free |
|---|---|---|
| Union | Closed | Closed |
| Concatenation, star | Closed | Closed |
| Intersection | Closed | NOT closed |
| Complement | Closed | NOT closed |
| Intersection with a regular language | Closed | Closed — the useful exception |
🧠 One witness proves two failures
Take L₁ = {aⁿbⁿcᵐ} and L₂ = {aᵐbⁿcⁿ}. Each is context free: the first matches a against b and lets c run free, the second ignores a and matches b against c, and each needs only one stack. Their intersection forces all three counts equal — {aⁿbⁿcⁿ} — which is not context free. That settles intersection. Complement then follows without a new example: if CFLs were closed under complement, then since they are closed under union, De Morgan would give closure under intersection, and we have just seen that fails. So one counterexample refutes both, and it is worth carrying in exactly this form rather than reconstructing it. The last row of the table is the exception that gets used constructively: CFL ∩ regular is always context free, which is how a PDA is combined with a finite automaton in practice.The Pumping Lemmas, and What They Can Prove
The regular pumping lemma says: if L is regular there is a length p such that every w in L with |w| ≥ p splits as xyz with |xy| ≤ p, |y| ≥ 1, and xyⁱz in L for every i ≥ 0. To refute regularity, pick a w that defeats every legal split. For {aⁿbⁿ} take w = aᵖbᵖ: the constraint |xy| ≤ p forces y to lie entirely inside the a-block, so pumping it adds a's without b's and leaves the language. The context-free version splits into uvxyz with |vxy| ≤ p and pumps v and y together, and for {aⁿbⁿcⁿ} the window vxy is too short to touch all three blocks, so pumping unbalances whichever two it misses.
⚠️ A pumping lemma can refute and can never confirm
The lemma has the form "if L is regular then L pumps". So a language that fails to pump is certainly not regular — that is a valid contrapositive and it is what the lemma is for. But a language that does pump has proved nothing: the converse is false, and there exist non-regular languages satisfying the pumping condition. So "I pumped it successfully, therefore it is regular" is invalid, and an option offering that reasoning is wrong however plausible it reads. When you actually want to prove regularity, build a DFA or a regular expression, or count Myhill–Nerode classes and find the number finite. The same asymmetry applies verbatim to the context-free pumping lemma. Knowing which direction a tool works in is worth more here than fluency in applying it.Key takeaways
- A PDA is a finite automaton plus one stack, and one stack matches exactly one pair of counts.
- {aⁿbⁿ} is context free and non-regular; {aⁿbⁿcⁿ} is not context free — two pairs, one stack.
- A stack returns symbols reversed, so {wwᴿ} is context free and {ww} is not.
- CFLs are closed under union, concatenation and star but NOT intersection or complement.
- The witness: {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}, and complement then fails by De Morgan.
- CFL ∩ regular IS context free — the exception that gets used constructively.
- For {aⁿbⁿ} pump w = aᵖbᵖ: |xy| ≤ p forces y inside the a-block.
- A pumping lemma refutes membership of a class and never confirms it — the converse is false.
Practice questions (8)
Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.
Which pair of context-free languages has an intersection that is not context free?
Show answer
Answer: B — {aⁿbⁿcᵐ} and {aᵐbⁿcⁿ}
Each of {aⁿbⁿcᵐ} and {aᵐbⁿcⁿ} needs one stack — the first matches a against b, the second b against c — so both are context free. Their intersection requires all three counts equal, giving {aⁿbⁿcⁿ}, which is not context free because one stack cannot check two pairs. Option D intersects a CFL with a regular language, and that is always context free — the one closure that does survive. Option C intersects two regular languages, which is regular. This single example also settles complement: closure under complement plus the union closure CFLs do have would give intersection closure by De Morgan, so complement fails too.Why is {wwᴿ : w ∈ {a,b}} context free while {ww : w ∈ {a,b}} is not?
Show answer
Answer: B — Because a stack returns symbols in reverse order
A stack is last-in-first-out, so pushing the first half and popping it against the second half compares them in opposite order — precisely what wwᴿ needs. Matching ww would require the pushed symbols back in the order they went in, which a stack cannot provide: the first symbol pushed is the last available. Option C is false — {wwᴿ} is context free and not regular, and a candidate who believes it regular will also mis-answer questions about the pumping lemma applied to it. The two languages look nearly identical on paper, so reading for the direction of the match is the habit that separates them.Context-free languages are closed under which of the following? (More than one may be correct.)
Show answer
Answer: A — Union; B — Intersection with a regular language
A and B. Union is easy — add a new start symbol deriving either grammar's start symbol. Intersection with a regular language is the useful exception: run the PDA and the finite automaton simultaneously in a product construction, and since the DFA needs no stack the result is still a PDA. C is false, by the witness {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}. D is false and follows from C without a new example, since union closure plus complement closure would give intersection closure by De Morgan. The contrast with regular languages — closed under all four — is the whole point of learning these as a set rather than one at a time.A language satisfies the conditions of the regular pumping lemma. It follows that the language:
Show answer
Answer: B — May or may not be regular
The lemma states "if L is regular then L pumps". Its valid use is the contrapositive: a language that fails to pump is certainly not regular. The converse is not a theorem, and non-regular languages satisfying the pumping condition exist — so pumping successfully establishes nothing at all, and the honest answer is B. This is a favourite question because option A is the natural misreading of a conditional, and getting it right is not a matter of skill with the lemma but of knowing which direction it runs in. To actually prove a language regular, exhibit a DFA or a regular expression, or show the Myhill–Nerode classes are finite in number.To show {aⁿbⁿ : n ≥ 0} is not regular using the pumping lemma with pumping length p, the string to choose is:
Show answer
Answer: A — aᵖbᵖ
aᵖbᵖ. It is in the language and long enough, and the constraint |xy| ≤ p forces the pumped block y to sit entirely inside the a-region — so pumping adds a's without matching b's and leaves the language, defeating every legal split at once. Option B is not in the language at all, so it proves nothing. Option C is too short for the lemma to apply. Option D is not in the language either — the b's come first. The general lesson is that choosing the witness string is the whole of the work: pick one where the |xy| ≤ p window is trapped in a region that must stay balanced.The language {aⁿbⁿcⁿ : n ≥ 1} is:
Show answer
Answer: C — Not context free
Not context free. A PDA has one stack, and checking the a's against the b's consumes it entirely — leaving nothing to check the c's. The context-free pumping lemma makes it formal: the window |vxy| ≤ p cannot span all three blocks, so pumping unbalances the ones it misses. Option D is wrong and worth being clear about: the language is easily decidable by a Turing machine, which can move back and forth over the tape as often as it likes, so it sits comfortably in a class above context free. That gap between "one stack" and "a tape" is exactly what the next chapter is about.The intersection of a context-free language with a regular language is:
Show answer
Answer: B — Always context free
Always context free, and this is the exception that makes the closure table useful rather than only cautionary. Run the PDA and the DFA side by side as a product machine: the DFA contributes states but needs no stack, so the combination is still a one-stack machine. Option A overreaches — {aⁿbⁿ} ∩ ab is {aⁿbⁿ} itself, which is not regular. The practical value is that it is the standard way to restrict a CFL: intersecting with a regular language lets you carve out a case without leaving the class, which is exactly what an argument about a CFL usually needs.A deterministic PDA is strictly less powerful than a nondeterministic one. Which language shows this?
Show answer
Answer: B — Even-length palindromes over {a, b}
The palindromes. A nondeterministic PDA guesses where the midpoint is, pushes the first half and pops against the second; a deterministic machine has no way to know when the middle has arrived, and no DPDA recognises the language. This is the sharp contrast with finite automata, where determinism costs only size: here it costs power, and that difference between the two models is a favourite exam point. {aⁿbⁿ} has a perfectly good DPDA — switch from pushing to popping when the first b appears — so option A is not a witness, and {aⁿbⁿcⁿ} is outside both classes.