Question 22

Given that $L_1$ is regular and $L_2$ is context-free:

• Regular languages are closed under complementation, union, and intersection.
• Context-free languages (CFLs) are closed under union, but are NOT closed under intersection or complementation.
• The intersection of a regular language and a context-free language is always a context-free language.

Analyze each option:

• Option A: $L_1 \cap \overline{L_2}$. Because CFLs are not closed under complementation, $\overline{L_2}$ is not necessarily a CFL. If $L_1 = \Sigma^*$, then $L_1 \cap \overline{L_2} = \overline{L_2}$, which need not be context-free. Thus, option A is not necessarily context-free.

• Option B: $\overline{\overline{L_1} \cup \overline{L_2}}$. By De Morgan's laws, $\overline{\overline{L_1} \cup \overline{L_2}} = L_1 \cap L_2$. Because the intersection of a regular language $L_1$ and a context-free language $L_2$ is always context-free, this language is always context-free. Option B is correct.

• Option C: $L_1 \cup (L_2 \cup \overline{L_1})$. By associativity and commutativity of union, this simplifies to $(L_1 \cup \overline{L_1}) \cup L_2 = \Sigma^* \cup L_2 = \Sigma^*$. Since $\Sigma^*$ is regular, it is also context-free. Option C is correct.

• Option D: $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$. Using the distributive law of intersection over union:

Since $L_2$ is given to be context-free, this language is context-free. Option D is correct.