PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q9

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: CFL Closure, Pumping Lemma & Decision Algorithms

Question

Explain the closure properties of context free language with suitable example.

Solution

Closed Operations for Context-Free Languages: Context-Free Languages (CFLs) are closed under the following operations. Let and be CFLs generated by grammars with start symbols and and disjoint variable sets:

  1. Union (): Closed. Create new start symbol .
    • Example: and are both CFLs. Their union is a CFL generated by .
  2. Concatenation (): Closed. Create new start symbol .
    • Example: If and , is a CFL.
  3. Kleene Star (): Closed. Create new start symbol .
    • Example: is context-free.

Non-Closed Operations and Counterexamples: CFLs are not closed under intersection and complementation:

  1. Intersection (): NOT closed.
    • Counterexample: Consider the two known CFLs:

Their intersection is:

By the Pumping Lemma for CFLs, is not context-free.

  1. Complementation (): NOT closed.
    • Reasoning: By De Morgan's Law, . If CFLs were closed under complementation, closure under union would imply closure under intersection, which is false.

(Note: CFLs are closed under intersection with a regular language: if is CFL and is regular, is a CFL).

Answer:

CFLs are closed under union, concatenation, and Kleene star via grammar composition. They are not closed under intersection (e.g., is not CFL) and complementation.

All past exam questions for Theory of Computation