GATE 2024 CS1 Q.23: solution and answer

GATE 2024 · CS1Q.23 · 1 mark · MSQ

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?

(A)
$L_{1} = L_{2}$ if and only if $L_{1} \cap \overline{L_{2}} = ϕ$
(B)
$L_{1} \cup L_{3}$ is not regular
(C)
$\overline{L_{3}}$ is not regular
(D)
$\overline{L_{1}} \cup \overline{L_{2}}$ is regular

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The always-true statements are (C) and (D).

Official answer: C, DSource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

Regular languages are closed under complement, union and intersection. Test each statement against these closure properties and, where it fails, a counterexample.
(A) $L_{1} \cap \overline{L_{2}} = ϕ$ means no string of $L_{1}$ lies outside $L_{2}$ , that is $L_{1} \subseteq L_{2}$ . This does not give equality. Take $L_{1} = {a}$ , $L_{2} = {a, b}$ : the intersection is empty but $L_{1} \neq = L_{2}$ . So the 'only if' direction fails and (A) is not always true.
(B) Take $L_{1} = Σ^{*}$ (regular) and any non-regular $L_{3}$ . Then $Σ^{*} \cup L_{3} = Σ^{*}$ , which is regular. So (B) is not always true.
(C) If $\overline{L_{3}}$ were regular, then $L_{3} = \overline{\overline{L_{3}}}$ would be regular by closure under complement. That contradicts the hypothesis, so $\overline{L_{3}}$ is not regular. (C) is always true.
(D) $\overline{L_{1}}$ and $\overline{L_{2}}$ are regular by closure under complement, and their union is regular by closure under union. (D) is always true.
Correct options: (C) and (D).

KEY IDEA

Regular languages are closed under complement and union, so complementing a non-regular language keeps it non-regular, and a union of complements of regular languages stays regular.

WATCH OUT FOR

Reading $L_{1} \cap \overline{L_{2}} = ϕ$ as $L_{1} = L_{2}$ . It only says $L_{1} \subseteq L_{2}$ . Another slip is assuming a union with a non-regular language is non-regular, when $L_{1} = Σ^{*}$ absorbs it.

From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 5 Regular languages questions, with notes

GATE 2024 CS1 Q.23: solution and answer

Answer and solution

More Regular languages questions