Question 11

Let $L_1$ be regular and $L_2$ be context-free (CFL). We evaluate each option:

• Option A: $L_1 \cap L_2$. The intersection of a regular language and a CFL is always a CFL. (True)
• Option B: $L_2 - L_1 = L_2 \cap \overline{L_1}$. Because $L_1$ is regular, its complement $\overline{L_1}$ is also regular. The intersection of a CFL with a regular language is always a CFL. (True)
• Option D: $L_1 \cup L_2$. The union of two CFLs (noting that every regular language is a CFL) is always a CFL. (True)

Now consider Option C: $L_1 - L_2 = L_1 \cap \overline{L_2}$. CFLs are not closed under complementation. If we choose $L_1 = \Sigma^*$ (which is regular), then $L_1 - L_2 = \Sigma^* - L_2 = \overline{L_2}$.

Since the complement of a CFL is not necessarily context-free, $L_1 - L_2$ is NOT necessarily context-free. Hence, option C is the correct answer.