GATE CS 2026 Set 1 Q.51: Context-Free Grammars, Pushdown Automata and CFLs

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?

$L_1$ is regular

$L_1 \cup L_2$ is regular

$L_2$ is context-free

$L_1$ is context-free

Official answer and solution

Solution

Use the inclusion of regular languages in context-free languages and construct a counterexample with $L_2 = \emptyset$ for $L_1$ .

Option (C) is always true: Since $L_2$ is given to be a regular language, and every regular language is also context-free ( $\text{REG} \subsetneq \text{CFL}$ ), $L_2$ is always context-free.
Options (A), (B), and (D) are false: Take $L_2 = \emptyset$ (regular) and let $L_1$ be any non-context-free (or undecidable) language. Then $L_1 \cap L_2 = \emptyset$ is regular, but $L_1 = L_1 \cup L_2$ is neither regular nor context-free.

Final answer

Option (C)

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

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 51 of 65
Section: Computer Science and Information Technology

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