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

We analyze each statement based on the closure properties and acceptance models of Context-Free Languages (CFLs):

• Option A is false: The set of languages accepted by Deterministic Pushdown Automata (DPDAs) is the class of Deterministic CFLs (DCFLs), which is a proper subset of CFLs. For example, the language $L = \{ww^R \mid w \in \{a, b\}^*\}$ is a CFL but cannot be accepted by any DPDA.
• Option B is true: CFLs are closed under union. If $L_1$ and $L_2$ are CFLs with start symbols $S_1$ and $S_2$ respectively, we can define a new grammar with start symbol $S$ and production $S \rightarrow S_1 \mid S_2$ to generate $L_1 \cup L_2$.
• Option C is false: 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.
• Option D is false: CFLs are not closed under complementation. If they were, they would also be closed under intersection because of De Morgan's Law: $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$, which contradicts the fact that CFLs are not closed under intersection.