GATE 2026 CS1 Q.51: solution and answer

GATE 2026 · CS1Q.51 · 2 marks · MSQ

Let $L_{1}$ and $L_{2}$ be two languages over a finite alphabet, such that $L_{1} \cap L_{2}$ and $L_{2}$ are regular languages.

Which of the following statements is/are always true?

(A)
$L_{1}$ is regular
(B)
$L_{1} \cup L_{2}$ is regular
(C)
$\overline{L_{2}}$ is context-free
(D)
$L_{1}$ is context-free

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Only option (C) is always true.

Official answer: CSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

The only facts given are that $L_{1} \cap L_{2}$ and $L_{2}$ are regular. Nothing else is assumed about $L_{1}$ , so a statement is "always true" only if it holds for every pair $(L_{1}, L_{2})$ that satisfies these two conditions.
Counterexample for $L_{1}$ : take $L_{2} = \emptyset$ , which is regular. Let $L_{1}$ be any language that is not regular. Then $L_{1} \cap L_{2} = \emptyset$ is regular, so both hypotheses hold while $L_{1}$ is arbitrary.
(A) $L_{1}$ is regular: false. With $L_{2} = \emptyset$ and $L_{1} = {a^{n} b^{n} ∣ n \geq 0}$ , the hypotheses hold but $L_{1}$ is not regular.
(D) $L_{1}$ is context-free: false. With $L_{2} = \emptyset$ and $L_{1} = {a^{n} b^{n} c^{n} ∣ n \geq 0}$ , which is not context-free, the hypotheses hold but $L_{1}$ is not context-free.
(B) $L_{1} \cup L_{2}$ is regular: false. With $L_{2} = \emptyset$ we get $L_{1} \cup L_{2} = L_{1}$ , which is not regular for the chosen $L_{1}$ . Note that $(L_{1} \cap L_{2}) \cup L_{2} = L_{2}$ , which is not the same set as $L_{1} \cup L_{2}$ .
(C) $\overline{L_{2}}$ is context-free: true. Regular languages are closed under complement (swap the accepting and non-accepting states of a complete DFA), so $\overline{L_{2}}$ is regular. Every regular language is context-free, so $\overline{L_{2}}$ is context-free for every valid choice of $L_{1}$ and $L_{2}$ .
Only (C) is always true.

KEY IDEA

The hypotheses constrain only $L_{2}$ and the intersection, so $L_{1}$ can be any language, for example when $L_{2} = \emptyset$ . Only a statement that depends on $L_{2}$ alone can be always true. Regular languages are closed under complement and are a subset of the context-free languages.

WATCH OUT FOR

Reading $L_{1} \cap L_{2}$ regular as a restriction on $L_{1}$ . Another slip is treating $(L_{1} \cap L_{2}) \cup L_{2}$ as $L_{1} \cup L_{2}$ and concluding (B). The union simplifies to $L_{2}$ , not $L_{1} \cup L_{2}$ .

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

GATE 2026 CS1 Q.51: solution and answer

Answer and solution

More Regular languages questions