Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE?

Let us analyze each statement:

• (A) is False: $L_1 \cap \overline{L_2} = \phi$ is equivalent to $L_1 \subseteq L_2$. For $L_1 = L_2$, we require both $L_1 \subseteq L_2$ and $L_2 \subseteq L_1$ (i.e., $(L_1 \cap \overline{L_2}) \cup (L_2 \cap \overline{L_1}) = \phi$). Hence, $L_1 \cap \overline{L_2} = \phi$ alone does not imply $L_1 = L_2$.

• (B) is False: The union of a regular language and a non-regular language can be regular. For example, choose $L_1 = \Sigma^*$ (regular) and $L_3 = \{a^n b^n \mid n \ge 0\}$ (non-regular). Then $L_1 \cup L_3 = \Sigma^*$, which is regular.

• (C) is True: Regular languages are closed under complementation. If $\overline{L_3}$ were regular, then its complement $\overline{\overline{L_3}} = L_3$ would also have to be regular, contradicting the fact that $L_3$ is not regular. Therefore, $\overline{L_3}$ must not be regular.

• (D) is True: Regular languages are closed under complementation and union. Since $L_1$ and $L_2$ are regular, $\overline{L_1}$ and $\overline{L_2}$ are regular, and their union $\overline{L_1} \cup \overline{L_2}$ is regular.

Thus, statements C and D are always TRUE.