GATE CS 2024 Set 1 Q.23: Regular Expressions, Finite Automata and Regular Languages

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?

$L_1 = L_2$ if and only if $L_1 \cap \overline{L_2} = \phi$

$L_1 \cup L_3$ is not regular

$\overline{L_3}$ is not regular

$\overline{L_1} \cup \overline{L_2}$ is regular

Official answer and solution

Solution

Apply set theory and the closure properties of regular languages under union and complementation.

(A) is FALSE: $L_1 \cap \overline{L_2} = \emptyset$ is equivalent to $L_1 \subseteq L_2$ , not $L_1 = L_2$ (for example, $L_1 = \emptyset$ and $L_2 = \Sigma^*$ satisfy $L_1 \cap \overline{L_2} = \emptyset$ , but $L_1 \neq L_2$ ).
(B) is FALSE: If $L_1 = \Sigma^*$ (which is 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 $\overline{\overline{L_3}} = L_3$ would also be regular, contradicting that $L_3$ is not regular.
(D) is TRUE: Since $L_1$ and $L_2$ are regular and regular languages are closed under complementation and union, $\overline{L_1} \cup \overline{L_2}$ is always regular.

Final answer

Options (C), (D)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.