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

Step 1: Understanding decidability.
A problem is decidable if there exists an algorithm that always terminates with a correct yes or no answer for all inputs.
Step 2: Analyzing each option.
Deciding whether a string belongs to a CFG language is decidable using parsing algorithms like CYK.
Checking whether a CFG generates an empty language is decidable.
Checking whether a CFG generates a finite language is also decidable.
Step 3: Identifying the undecidable problem.
Determining whether a context-free grammar is ambiguous is a well-known undecidable problem in formal language theory. There is no algorithm that can solve this for all CFGs.
Step 4: Final conclusion.
Hence, the undecidable problem is deciding whether a given context-free grammar is ambiguous.