Questions: Closure Properties of Context-Free Languages

Question 1

Consider L₁ = {aⁿbⁿcᵐ | n, m ≥ 0} and L₂ = {aᵐbⁿcⁿ | n, m ≥ 0}. Both are context-free languages. Their intersection is {aⁿbⁿcⁿ | n ≥ 0}. What does this example prove?

• A. That context-free languages are not closed under union
• B. That context-free languages are not closed under concatenation
• C. That context-free languages are not closed under intersection
• D. That {aⁿbⁿcⁿ} is a context-free language

Answer: (C)

Each language individually is context-free: a PDA for L₁ uses its stack to match a's with b's while ignoring c's; a PDA for L₂ uses its stack to match b's with c's while ignoring a's. But their intersection {aⁿbⁿcⁿ} requires matching all three groups simultaneously — something no single pushdown stack can do, as the pumping lemma for CFLs demonstrates. Since two CFLs produced a non-CFL intersection, CFLs are not closed under intersection. Option D would be wrong — {aⁿbⁿcⁿ} is the canonical example of a language that is NOT context-free.

Question 2

To prove that CFLs are not closed under complement, the most elegant argument uses:

• A. Constructing an explicit CFL whose complement is demonstrably non-context-free
• B. De Morgan's laws combined with closure under union and non-closure under intersection
• C. The pumping lemma for CFLs applied to the complement of {aⁿbⁿcⁿ}
• D. A diagonalization argument analogous to Cantor's proof

Answer: (B)

The argument is: suppose CFLs were closed under complement. Then for any two CFLs A and B, we could compute ¬A and ¬B (both CFLs by assumption), take their union ¬A ∪ ¬B (CFL by closure under union), and complement the result: ¬(¬A ∪ ¬B) = A ∩ B by De Morgan. That would make A ∩ B a CFL — but we know intersection is not closed. Contradiction. Therefore the assumption was wrong: CFLs are not closed under complement. This is an indirect proof that does not require exhibiting a specific CFL with a non-CFL complement.

Question 3

Context-free languages, like regular languages, are closed under complement.

• T. True
• F. False

Answer: False

This is a critical distinction between regular and context-free languages. Regular languages enjoy closure under all Boolean operations: union, intersection, and complement. CFLs are closed under union but fail for both intersection and complement. The failure of complement closure follows from the failure of intersection closure via De Morgan's laws: if CFLs were closed under complement, closure under union would force closure under intersection — a contradiction. Students who internalize regular language closure properties sometimes assume CFLs behave the same way, but the stack's limited memory creates exactly these gaps.

Question 4

The intersection of a context-free language with a regular language is always context-free, even though the intersection of two context-free languages is not always context-free.

• T. True
• F. False

Answer: True

This asymmetry is important and practically useful. The proof is constructive: build a product machine that runs a PDA (for the CFL) and a DFA (for the regular language) in parallel. The PDA handles the context-free constraint using its stack; the DFA simultaneously tracks the regular constraint using its finite state. Acceptance requires both components to accept. The result is a PDA, so the intersection is context-free. This works because a DFA adds no memory requirements — it can ride alongside the PDA without demanding a second stack. The result fails for two CFLs because combining two PDAs generally requires two stacks, which is more powerful than a single stack.

Question 5

Why does the failure of CFLs to be closed under intersection imply they are also not closed under complement?

Model answer: The connection runs through De Morgan's laws: A ∩ B = ¬(¬A ∪ ¬B). If CFLs were closed under complement, then for any two CFLs A and B, their complements ¬A and ¬B would also be CFLs. CFLs are closed under union, so ¬A ∪ ¬B would be a CFL. Applying complement closure again, ¬(¬A ∪ ¬B) = A ∩ B would be a CFL. But we know A ∩ B is not always a CFL — the {aⁿbⁿcⁿ} counterexample shows two CFLs whose intersection is not context-free. This contradiction means our assumption was wrong: CFLs cannot be closed under complement.

This is a standard technique in formal language theory: use known closure properties as constraints to infer non-closure. The argument is indirect (proof by contradiction) and shows that intersection closure and complement closure are not independent — if you have union closure, they stand or fall together. Regular languages happen to have all three; CFLs have only union, so neither intersection nor complement closure holds.