GATE CS 2025 Set 2 | Question 25
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?
Explanation
Answer: (D)
Emptiness of a CFG is decidable. Mark every variable that can derive a string of terminals: first those with a production whose body has only terminals (or is \(\varepsilon\)), then, repeatedly, any variable with a body made of terminals and marked variables. \(L(G_{1}) = \emptyset\) exactly when the start symbol is never marked, and the marking stops after at most as many rounds as there are variables. So (D) is decidable.
The other three are undecidable for CFGs:
- (A) equivalence of two CFGs;
- (B) whether two context-free languages share a string;
- (C) with \(R = \Sigma^{*}\), it asks whether \(G_{1}\) generates every string, which is undecidable.
Answer: D