GATE CS 2007 Q6 — Undecidability

To determine which of the given problems is undecidable, let us analyze each option:

• A. Membership problem for CFGs: Decidable. Given a Context-Free Grammar (CFG) $G$ and a string $w$, we can decide whether $w \in L(G)$ using parsing algorithms like the CYK algorithm, which runs in $O(|w|^3)$ time.
• B. Ambiguity problem for CFGs: Undecidable. There is no algorithm to determine whether an arbitrary CFG is ambiguous (i.e., whether there exists some string in the language with more than one leftmost derivation). This is a classic undecidable problem, typically proven via reduction from the Post Correspondence Problem (PCP).
• C. Finiteness problem for FSAs: Decidable. For a Finite State Automaton (FSA), we can check if its language is finite by verifying if there is a cycle reachable from the start state that can also reach an accepting state. Since the state graph is finite, this can be done using standard graph traversal algorithms (like DFS/BFS).
• D. Equivalence problem for FSAs: Decidable. Given two FSAs $A$ and $B$, we can construct a product automaton representing the symmetric difference:
  $$L(C) = (L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B))$$
  Since regular languages are closed under complement, intersection, and union, $C$ is also an FSA. We then test if $L(C) = \emptyset$, which is decidable.

Therefore, the ambiguity problem for CFGs is the only undecidable problem among the choices.