GATE CS 2024 Set 1 Q13 — Regular and Context-free Languages

We are given that $L_1$ and $L_2$ are regular languages, and $L_3$ is a non-regular language.

Let's analyze each option systematically:

• Option A: $L_1 = L_2$ if and only if $L_1 \cap \overline{L_2} = \phi$
  The condition $L_1 \cap \overline{L_2} = \phi$ is equivalent to $L_1 \subseteq L_2$. This does not imply $L_1 = L_2$.
  Counterexample: Let $L_1 = \phi$ and $L_2 = \Sigma^*$. Both are regular. Here, $L_1 \cap \overline{L_2} = \phi \cap \phi = \phi$, but $L_1 \neq L_2$. Thus, this statement is FALSE.


• Option B: $L_1 \cup L_3$ is not regular
  The union of a regular language and a non-regular language can sometimes be regular.
  Counterexample: Let $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. Thus, this statement is FALSE.


• Option C: $\overline{L_3}$ is not regular
  Regular languages are closed under complementation. If $\overline{L_3}$ were regular, then its complement $\overline{\overline{L_3}} = L_3$ would also be regular. Since we are given that $L_3$ is not regular, $\overline{L_3}$ must also be non-regular. Thus, this statement is ALWAYS TRUE.


• Option D: $\overline{L_1} \cup \overline{L_2}$ is regular
  Since $L_1$ and $L_2$ are regular:
  • $\overline{L_1}$ and $\overline{L_2}$ are regular (closure under complementation).
  • $\overline{L_1} \cup \overline{L_2}$ is regular (closure under union).
  Thus, this statement is ALWAYS TRUE.