GATE 2025 CS2 Q.25: solution and answer

GATE 2025 · CS2Q.25 · 1 mark · MCQ

Let $G_{1}, G_{2}$ be Context Free Grammars (CFGs) and $R$ be a regular expression. For a grammar $G$ , let $L (G)$ denote the language generated by $G$ .

Which ONE among the following questions is decidable?

(A)
Is $L (G_{1}) = L (G_{2})$ ?
(B)
Is $L (G_{1}) \cap L (G_{2}) = \emptyset$ ?
(C)
Is $L (G_{1}) = L (R)$ ?
(D)
Is $L (G_{1}) = \emptyset$ ?

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The decidable question is (D): whether $L (G_{1}) = \emptyset$ .

Official answer: DSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

Recall the decidability results for context-free languages. Emptiness, finiteness and membership are decidable. Equivalence of two CFGs, universality ( $L = Σ^{*}$ ) and emptiness of an intersection of two CFLs are undecidable.
(A) $L (G_{1}) = L (G_{2})$ is the equivalence problem for CFGs, which is undecidable.
(B) $L (G_{1}) \cap L (G_{2}) = \emptyset$ is undecidable. Post's Correspondence Problem reduces to it: for a PCP instance one can build two CFGs whose languages intersect exactly when the instance has a solution.
(C) $L (G_{1}) = L (R)$ is undecidable. Take $R = Σ^{*}$ . The question becomes whether $L (G_{1}) = Σ^{*}$ , which is CFG universality, and that is undecidable. A problem that is undecidable for one choice of $R$ is undecidable in general.
(D) $L (G_{1}) = \emptyset$ is decidable. Compute the set of generating variables. Start with the variables that have a production whose right side contains only terminals. Repeatedly add a variable that has a production whose right side contains only terminals and variables already in the set. The set grows at most once per variable, so this stops after finitely many rounds. Then $L (G_{1}) \neq = \emptyset$ exactly when the start symbol $S$ is in the set.
Only (D) is decidable, so the answer is (D).

KEY IDEA

Emptiness of a CFG is decidable by finding the generating variables and checking whether the start symbol is one of them. Equivalence, universality and intersection-emptiness for CFLs are undecidable.

WATCH OUT FOR

Treating (C) as decidable because $R$ is regular. Regular-versus-CFL equality is still undecidable, because choosing $R = Σ^{*}$ gives CFG universality. Another slip is assuming (B) is decidable because the emptiness of one CFL is.

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 8 Turing machines questions, with notes

GATE 2025 CS2 Q.25: solution and answer

Answer and solution

More Turing machines questions