Past exam question: 2082 Kartik (Back), Q3(a)
Open in the Padhaiko appShow that the context free language are not closed under intersection and complementation but closed under Kleene star.
Solution
Proof of Closure under Kleene Star: Let be a context-free language generated by CFG .
To show that is context-free, construct a new grammar where is a new start symbol, and contains the production rules:
- Base case: .
- Recursive generation: where each .
Since is a valid context-free grammar, is a context-free language. Thus, CFLs are closed under Kleene star.
Proof that CFLs are Not Closed under Intersection: We prove by counterexample. Consider the two languages:
- is context-free: generated by , , .
- is context-free: generated by , , .
Now consider their intersection:
By the Pumping Lemma for Context-Free Languages, is not context-free. Hence, CFLs are not closed under intersection.
Proof that CFLs are Not Closed under Complementation: We prove by contradiction using De Morgan's Laws. Recall that CFLs are closed under union ().
Assume for contradiction that CFLs were closed under complementation. Then for any two CFLs and , their complements and would also be CFLs.
By closure under union, would be a CFL. By closure under complementation once more, the complement:
would have to be a CFL. But this contradicts our established result that CFLs are not closed under intersection. Therefore, CFLs are not closed under complementation.
CFLs are closed under Kleene star via . They are not closed under intersection because (not CFL). By De Morgan's Law, this non-closure directly implies that CFLs are also not closed under complementation.