Question 4

Evaluate each statement:

• Statement I ($L_1 \cup L_2$ is context-free): Context-free languages are closed under union. If $S_1, S_2$ are start symbols of grammars for $L_1, L_2$, we can introduce $S \to S_1 \mid S_2$. Thus, Statement I is CORRECT.
• Statement II ($\overline{L_1}$ is context-free): CFLs are not closed under complementation. For example, $L = \{a^n b^n c^n \mid n \ge 1\}$ is not context-free, but its complement $\overline{L}$ is context-free. Thus, the complement of a CFL is not necessarily context-free. Statement II is INCORRECT.
• Statement III ($L_1 - R$ is context-free): Note that $L_1 - R = L_1 \cap \overline{R}$. Since $R$ is regular, its complement $\overline{R}$ is also regular. The intersection of a context-free language with a regular language is always context-free. Thus, Statement III is CORRECT.
• Statement IV ($L_1 \cap L_2$ is context-free): CFLs are not closed under intersection. For instance, $L_1 = \{a^n b^n c^m\}$ and $L_2 = \{a^m b^n c^n\}$ are both CFLs, but $L_1 \cap L_2 = \{a^n b^n c^n\}$ is not context-free. Statement IV is INCORRECT.

Therefore, statements I and III only are correct, which corresponds to option B.