GATE CS 2017 Set 2 Q04 — Regular and Context-free Languages

To determine which statements are correct, let us analyze the closure properties of Context-Free Languages (CFLs):

• Statement I: $L_1 \cup L_2$ is context-free.
  CORRECT. Context-free languages are closed under union. If $S_1$ and $S_2$ are the start symbols of the grammars generating $L_1$ and $L_2$ respectively, we can define a new start symbol $S \to S_1 \mid S_2$ to generate $L_1 \cup L_2$.


• Statement II: $\overline{L_1}$ is context-free.
  INCORRECT. CFLs are not closed under complementation. For example, the language $L = \{a^n b^n c^n \mid n \ge 0\}$ is not context-free, but its complement $\overline{L}$ is context-free.


• Statement III: $L_1 - R$ is context-free.
  CORRECT. We can rewrite the set difference as: $$L_1 - R = L_1 \cap \overline{R}$$ Since $R$ is a regular language, its complement $\overline{R}$ is also regular. CFLs are closed under intersection with regular languages. Since $L_1$ is a CFL and $\overline{R}$ is regular, their intersection $L_1 \cap \overline{R}$ is guaranteed to be a CFL.


• Statement IV: $L_1 \cap L_2$ is context-free.
  INCORRECT. 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.

Thus, only statements I and III are correct.