GATE CS 2021 Set 2 Q12 — Regular and Context-free Languages

Given that $L_1$ is a regular language and $L_2$ is a context-free language (CFL).

• Option A: $L_1 \cap \overline{L_2}$. Since CFLs are not closed under complementation, $\overline{L_2}$ is not necessarily a CFL. If we choose $L_1 = \Sigma^*$, then $L_1 \cap \overline{L_2} = \overline{L_2}$, which may not be a CFL. Thus, this is not always context-free.
• Option B: $\overline{\overline{L_1} \cup \overline{L_2}}$. Applying De Morgan's laws, this simplifies to $L_1 \cap L_2$. Since the intersection of a regular language and a CFL is always a CFL, this language is always context-free.
• Option C: $L_1 \cup (L_2 \cup \overline{L_2})$. Since $L_2 \cup \overline{L_2} = \Sigma^*$, the expression simplifies to $L_1 \cup \Sigma^* = \Sigma^*$. Since $\Sigma^*$ is regular, it is also context-free.
• Option D: $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$. Factoring out $L_2$ using the distributive law gives $(L_1 \cup \overline{L_1}) \cap L_2 = \Sigma^* \cap L_2 = L_2$. Since $L_2$ is a CFL, this language is always context-free.