Which of the following problems is undecidable?

Answer: The ambiguity problem for context-free grammars is undecidable.

What the ambiguity problem means: Given a context-free grammar, decide whether there exists any string in its language that has two or more distinct parse trees (i.e., two different leftmost or parse-tree derivations).

Why the other listed problems are decidable:

• Membership for context-free grammars: decidable by parsing algorithms such as CYK or Earley.

• Finiteness for finite-state automata: decidable by checking reachable states that can reach an accepting state and detecting cycles in that subgraph; a reachable cycle implies an infinite language.

• Equivalence for finite-state automata: decidable by constructing the product automaton for the symmetric difference and checking emptiness, or by determinizing and minimizing and then comparing.

Proof idea for undecidability of ambiguity:

• One standard approach is a reduction from the Post Correspondence Problem (PCP), which is known to be undecidable.

• Given an instance of PCP, construct a context-free grammar that produces a terminal string in two different ways exactly when the PCP instance has a solution. The construction encodes candidate tile sequences so that two different derivations correspond to the two matched sequences in PCP.

• Therefore, if one could decide ambiguity for arbitrary CFGs, one could decide PCP; because PCP is undecidable, ambiguity for CFGs must be undecidable.

Summary: The ambiguity problem for context-free grammars is undecidable; the other listed problems (membership for CFGs, finiteness for FSAs, and equivalence for FSAs) are decidable with standard algorithms.