GATE CS 2026 Set 1 Q41 — Regular and Context-free Languages

We are given that $L_2$ is a regular language and $L_1 \cap L_2$ is a regular language over a finite alphabet.

1. Analyzing Option C

• Since $L_2$ is a regular language, its complement $\overline{L_2}$ is also a regular language (as regular languages are closed under complementation).
• Every regular language is also a context-free language (since the class of regular languages is a proper subset of context-free languages).
• Therefore, $\overline{L_2}$ is always context-free. This statement is always true.

2. Counterexample for Options A, B, and D

To show that options A, B, and D are not always true, let us construct a counterexample:

• Let $L_1 = \{a^n b^n c^n \mid n \ge 0\}$, which is a well-known non-context-free (and hence non-regular) language.
• Let $L_2 = \emptyset$, which is a regular language.

Now, let's verify the given conditions:

• $L_2 = \emptyset$ is regular. (Satisfied)
• $L_1 \cap L_2 = L_1 \cap \emptyset = \emptyset$, which is regular. (Satisfied)

Under these valid conditions, let's evaluate the remaining options:

• Option A: $L_1$ is regular $\implies$ False, since $L_1 = \{a^n b^n c^n \mid n \ge 0\}$ is not regular.
• Option B: $L_1 \cup L_2 = L_1 \cup \emptyset = L_1$ is regular $\implies$ False.
• Option D: $L_1$ is context-free $\implies$ False, since $L_1$ is not context-free.

Thus, only option C is always true.