Which one of the following problems is undecidable?

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

Explanation: There is no algorithm that decides for every context-free grammar whether it is ambiguous (i.e., whether some string has two distinct parse trees). The standard proof constructs, from an instance of a known undecidable problem (for example, the Post Correspondence Problem), a grammar that is ambiguous exactly when the original instance has a solution. Because the source problem is undecidable, ambiguity for CFGs is undecidable as well.

• Membership (deciding if a given string is generated by a CFG): Decidable. Use parsing algorithms such as CYK (after converting the grammar to Chomsky Normal Form) or Earley's algorithm. CYK runs in polynomial time (O(n^3)).

• Emptiness (deciding if the language of a CFG is empty): Decidable. Compute the set of generating nonterminals by a fixed-point iteration: add any nonterminal that has a production whose right-hand side consists entirely of terminals and/or already-known generating nonterminals. The language is empty exactly when the start symbol is not in this set.

• Finiteness (deciding if the language of a CFG is finite): Decidable. Remove nonterminals that cannot derive terminal strings, then inspect the dependency graph of the remaining nonterminals. If there is a cycle reachable from the start symbol that can lead to unbounded growth in derivation length, the language is infinite; otherwise it is finite. This yields an effective decision procedure.