Question

Which one of the following problems is undecidable?

• A. Deciding if a given context-free grammar is ambiguous
• B. Deciding if a given string can be generated by a given context-free grammar
• C. Deciding if the language generated by a given context-free grammar is empty
• D. Deciding if the language generated by a given context-free grammar is finite

Hint:

Ambiguity checking for context-free grammars is undecidable, while membership and emptiness problems are decidable.

Answer 1

The Correct Option is A

Membership, emptiness, and finiteness are all "structural" questions about a CFG that can be answered by walking the grammar's productions in a bounded way, parsing a string bottom-up, or tracing which non-terminals can reach a terminal string or fall into a cycle, and each of these checks is guaranteed to finish.
Ambiguity is different in kind: it asks whether ANY string in the (possibly infinite) language has two different derivations, and there's no way to bound the search over all strings and all derivations for an arbitrary grammar. This has been formally shown to be unsolvable in general.
So the correct answer is deciding if a given context-free grammar is ambiguous.

Answer 2

Formal language theory has a well-studied list of "yes, this is decidable for CFGs" results, and it's useful to check each option against that list:

1. Ambiguity: This sits outside the list of positive decidability results for CFGs; it's one of the classic textbook examples of an undecidable property of context-free grammars.
2. String membership: This is one of the most basic decidable questions in the theory, it's the entire basis for how parsers in compilers work, and always terminates correctly.
3. Emptiness: Also firmly on the decidable list, it only requires checking reachability of terminal-deriving non-terminals in the grammar, a finite computation.
4. Finiteness: Also decidable, determined by checking whether the grammar contains a non-terminal that can derive a string containing itself (a self-embedding cycle); if none exists, the language is finite.

Ambiguity is the one property on this list that has no known (or possible) general algorithm.

Therefore, the correct answer is Deciding if a given context-free grammar is ambiguous.