GATE CS 1999 Q1.5 — Context-free Grammars and Push-down Automata

Context-free languages (CFLs) have specific closure properties under regular operations:

• Union: If $L_1$ and $L_2$ are CFLs, then $L_1 \cup L_2$ is also a CFL. This can be shown by creating a new start symbol $S \to S_1 \mid S_2$.
• Kleene Closure: If $L$ is a CFL, then $L^*$ is also a CFL. This can be shown by adding a production $S \to SS \mid \epsilon$.

However, CFLs are not closed under:

• Intersection: For example, $L_1 = \{a^n b^n c^m \mid n, m \ge 0\}$ and $L_2 = \{a^m b^n c^n \mid n, m \ge 0\}$ are both CFLs, but their intersection $L_1 \cap L_2 = \{a^n b^n c^n \mid n \ge 0\}$ is a well-known non-CFL.
• Complement: Since $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$, closure under union and complement would imply closure under intersection, which is a contradiction.

Evaluating the options:

• A: Closed under Union, but NOT Intersection.
• B: Closed under both Union and Kleene closure. (Correct)
• C: NOT closed under Intersection or Complement.
• D: NOT closed under Complement, though closed under Kleene closure.