GATE CS 1992 Q02 — Context-free Grammars and Push-down Automata

Context-Free Languages (CFLs) have specific closure properties under various operations:

• Closed under Union (Option A): If $L_1$ and $L_2$ are CFLs generated by grammars with start symbols $S_1$ and $S_2$ respectively, we can define a new start symbol $S \rightarrow S_1 \mid S_2$ to generate $L_1 \cup L_2$. Hence, CFLs are closed under union.
• Closed under Kleene closure (Option D): If $L$ is a CFL with start symbol $S_1$, we can define a new start symbol $S \rightarrow S_1 S \mid \epsilon$ to generate $L^*$. Hence, CFLs are closed under Kleene closure.
• Not closed under Intersection (Option C): For example, the languages $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 context-free, but their intersection $L_1 \cap L_2 = \{a^n b^n c^n \mid n \ge 0\}$ is a well-known non-context-free language.
• Not closed under Complementation (Option B): By De Morgan's Laws, if CFLs were closed under complementation, they would also be closed under intersection since $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$. Since they are not closed under intersection, they cannot be closed under complementation.

Thus, the correct options are A and D.