Let L 1 and L 2 be two languages over a finite alphabet, such that L 1 L 2 and L 2 are regular languages. Which of the following statements is/are true?

GATE 2026 CS (CS1) – Question 51

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Multiple select

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 true?

$L_1$ is regular
$L_1 \cup L_2$ is regular
$L_2$ is context-free
$L_1$ is context-free

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $L_2$ is context-free

Explanation

We are given that $L_2$ is regular and $L_1 \cap L_2$ is regular.
- Since every regular language is also a context-free language (regular languages are a proper subset of context-free languages), $L_2$ being regular immediately implies that $L_2$ is context-free. Hence, statement (C) is ALWAYS true.
- For $L_1$:
Let $L_2 = \emptyset$ (the empty language, which is regular). Then $L_1 \cap L_2 = \emptyset$, which is regular, regardless of what $L_1$ is. $L_1$ could be an undecidable language, a context-sensitive language, or any arbitrary non-context-free language (such as $\{a^n b^n c^n \mid n \ge 0\}$ or the Halting problem). In that case, neither $L_1$, $L_1 \cup L_2$, nor $L_1$ being context-free holds in general.

Therefore, only statement (C) is guaranteed to be true.