Past exam question: 2082 Chaitra (Regular), Q9
Open in the Padhaiko appQuestion
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:
- Union (): Closed. Create new start symbol .
- Example: and are both CFLs. Their union is a CFL generated by .
- Concatenation (): Closed. Create new start symbol .
- Example: If and , is a CFL.
- Kleene Star (): Closed. Create new start symbol .
- Example: is context-free.
Non-Closed Operations and Counterexamples: CFLs are not closed under intersection and complementation:
- Intersection (): NOT closed.
- Counterexample: Consider the two known CFLs:
Their intersection is:
By the Pumping Lemma for CFLs, is not context-free.
- 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.