GATE CS 2014 Set 3 Q35 — Undecidability

To determine which of the problems is undecidable, let us analyze each option for Context-Free Grammars (CFGs):

• Option A: Deciding if a given CFG is ambiguous.
  This is a well-known undecidable problem. There is no algorithm that can take an arbitrary CFG and determine whether it is ambiguous or not. This is typically proven by reducing the Post Correspondence Problem (PCP) to the CFG ambiguity problem.
• Option B: Deciding if a given string is generated by a given CFG (Membership Problem).
  This is decidable. For any CFG $G$ and string $w$, we can use parsing algorithms like the CYK algorithm (which runs in $O(|w|^3)$ time) to decide if $w \in L(G)$.
• Option C: Deciding if the language generated by a given CFG is empty (Emptiness Problem).
  This is decidable. We can compute the set of all generating variables in the grammar. If the start symbol $S$ is not a generating variable, then $L(G) = \emptyset$.
• Option D: Deciding if the language generated by a given CFG is finite (Finiteness Problem).
  This is decidable. After eliminating useless symbols, we can construct a directed graph representing the dependencies between variables. If the graph contains a cycle that can be reached from the start symbol and can reach a terminal string, the language is infinite; otherwise, it is finite.

Therefore, only the problem in Option A is undecidable.