GATE CS 2021 Set 2 — Question 22

We are 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}$
Context-free languages are not closed under complementation. Thus, $\overline{L_2}$ is not necessarily a CFL. The intersection of a regular language ($L_1$) and a non-CFL ($\overline{L_2}$) is not necessarily context-free. For example, if $L_1 = \Sigma^*$, then $L_1 \cap \overline{L_2} = \overline{L_2}$, which might not be CFL.Option (B): $\overline{L_1 \cup L_2}$
Since $L_1$ is regular, it is also context-free. The union of two CFLs ($L_1 \cup L_2$) is a CFL. However, the complement of a CFL is not necessarily a CFL. Thus, this language is not guaranteed to be context-free.Option (C): $L_1 \cup (L_2 \cup \overline{L_2})$
Note that for any language $L$, $L \cup \overline{L} = \Sigma^*$ (the set of all strings over the alphabet). Thus, $L_2 \cup \overline{L_2} = \Sigma^*$. The expression becomes $L_1 \cup \Sigma^* = \Sigma^*$. Since $\Sigma^*$ is a regular language, it is also context-free. This is always context-free.Option (D): $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$
We can factor out $L_2$ from the expression:
$(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2) = L_2 \cap (L_1 \cup \overline{L_1})$
Since $L_1 \cup \overline{L_1} = \Sigma^*$, the expression simplifies to:
$L_2 \cap \Sigma^* = L_2$
Since $L_2$ is given as a context-free language, the result is context-free.Alternatively, using closure properties:Therefore, options (C) and (D) are correct.