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.

Answer 2

Decidability here means whether an algorithm exists that always halts with a correct yes/no answer, for every possible context-free grammar given as input. Let's check each problem:

1. Deciding if a given context-free grammar is ambiguous: This asks whether some string in the language has two distinct parse trees (or leftmost derivations). No general algorithm can check this for every possible CFG, it has been proven that no such algorithm can exist, making this problem undecidable.
2. Deciding if a given string can be generated by a given context-free grammar: This is the membership problem, and it's solved routinely by parsing algorithms such as CYK or Earley's algorithm, which always terminate with a definite yes or no. This is decidable.
3. Deciding if the language generated by a given context-free grammar is empty: This can be checked by seeing whether the start symbol can ever derive a string of terminals, a straightforward reachability computation over the grammar's productions that always terminates. This is decidable.
4. Deciding if the language generated by a given context-free grammar is finite: This reduces to checking for certain cyclic/self-embedding patterns in the grammar's derivation graph, which can be checked algorithmically and always terminates. This is decidable.

Three of these four questions can be answered algorithmically for any CFG; only the ambiguity question has been proven to have no general algorithm.

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