GATE CS 2025 Set 2 Q15 — Undecidability

To determine which of the given questions is decidable, we analyze the decidability properties of Context-Free Languages (CFLs) represented by Context-Free Grammars (CFGs):

• Option A: Is $L(G_1) = L(G_2)$?
  The equivalence problem for two CFGs is undecidable. There is no algorithm to determine if two arbitrary CFGs generate the exact same language.
• Option B: Is $L(G_1) \cap L(G_2) = \emptyset$?
  The disjointness problem for two CFGs is undecidable. This can be shown by reduction from the Post Correspondence Problem (PCP).
• Option C: Is $L(G_1) = L(R)$?
  The problem of checking whether a CFG generates a given regular language is undecidable. In particular, testing if $L(G_1) = \Sigma^*$ (where $\Sigma^*$ is regular) is a well-known undecidable problem.
• Option D: Is $L(G_1) = \emptyset$?
  The emptiness problem for CFGs is decidable. We can determine if a CFG generates any terminal string by identifying "productive" variables (variables that can eventually derive a string of terminals). If the start symbol $S$ is productive, then $L(G_1) \neq \emptyset$; otherwise, $L(G_1) = \emptyset$. This algorithm always terminates in polynomial time.

Therefore, the only decidable question among the choices is D.