The GATE Grind

GATE 2025 CS (CS2) – Question 25

Theory of Computation · Turing Machines and Undecidability · 1 mark · Multiple choice

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?

  1. Is $L(G_1) = L(G_2)$?
  2. Is $L(G_1) \cap L(G_2) = \emptyset$?
  3. Is $L(G_1) = L(R)$?
  4. Is $L(G_1) = \emptyset$?

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) Is $L(G_1) = \emptyset$?

Explanation

Emptiness of a CFG is decidable by checking whether the start symbol is productive. Equivalence of CFGs, emptiness of the intersection of two CFLs, and equality of a CFL with a regular language are all undecidable.