GATE CS 2024 Set 1 — Question 23

MSQ+1 / -0MediumClosure Properties (Regular)Finite Automata & Regular LanguagesTheory of Computation

Theory of Computation → Finite Automata & Regular Languages → Closure Properties (Regular)

Last updated 20 August 2026

Question

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} = \emptyset

L_1 \cup L_3

is not regular

\overline{L_3}

is not regular

\overline{L_1} \cup \overline{L_2}

is regular

Let

L_1, L_2

be regular languages and

L_3

be a non-regular language.

Option (A): $L_1 = L_2$ if and only if $L_1 \cap \overline{L_2} = \emptyset$ . This is false. $L_1 \cap \overline{L_2} = \emptyset$ is equivalent to $L_1 \subseteq L_2$ . For $L_1 = L_2$ to be true, we also need $L_2 \cap \overline{L_1} = \emptyset$ (i.e., $L_2 \subseteq L_1$ ).
Option (B): $L_1 \cup L_3$ is not regular. This is false. For example, if $L_1 = \Sigma^*$ (which is regular) and $L_3$ is any non-regular language, then $L_1 \cup L_3 = \Sigma^*$ , which is regular.
Option (C): $\overline{L_3}$ is not regular. This 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 be regular, which contradicts the given that $L_3$ is not regular.
Option (D): $\overline{L_1} \cup \overline{L_2}$ is regular. This 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 also regular.

Therefore, the correct options are (C) and (D).