PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q3(a)

Theory of Computation · 4 marks

Open in the Padhaiko app

Topic: CFL Closure, Pumping Lemma & Decision Algorithms

Question

Show 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:

  1. Base case: .
  2. 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:

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.

Answer:

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.

All past exam questions for Theory of Computation