Which of the following problems is undecidable ?

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

Explanation:

• Determining if two finite automata are equivalent — Decidable. Construct the product automaton for the symmetric difference of their languages and check that the resulting language is empty; emptiness is decidable for finite automata.

• Membership problem for a context-free grammar — Decidable. Use the CYK algorithm after converting the grammar to Chomsky Normal Form; it decides whether a given string belongs to the grammar's language in polynomial time.

• Finiteness problem for a finite automaton — Decidable. Determine whether there is a cycle reachable from the start state that can also reach a final state; such a cycle implies infinitely many accepted strings, otherwise the language is finite.

• Ambiguity problem for a context-free grammar — Undecidable. There is no general algorithm that decides for every context-free grammar whether some string has more than one leftmost (or parse) derivation. Standard undecidability proofs reduce a known undecidable problem (for example, the Post Correspondence Problem) to grammar ambiguity.

Therefore the undecidable problem among the given choices is the ambiguity problem for context-free grammars.