GATE CS 2014 Set 3 Q.45 (CS Q.35): Decidability, Reducibility and Undecidability

Which one of the following problems is undecidable?

Deciding if a given context-free grammar is ambiguous.

Deciding if a given string is generated by a given context-free grammar.

Deciding if the language generated by a given context-free grammar is empty.

Deciding if the language generated by a given context-free grammar is finite.

Official answer and solution

Solution

Recall standard decidability and undecidability results for Context-Free Grammars.

Decidable Properties of CFGs:
- Membership problem ( $w \in L(G)$ ): Decidable in polynomial time using the CYK algorithm or Earley's parser ( $O(n^3)$ ). Hence option B is decidable.
- Emptiness problem ( $L(G) = \emptyset$ ): Decidable in polynomial time by finding whether the start symbol $S$ can generate any string of terminal symbols. Hence option C is decidable.
- Finiteness problem ( $|L(G)| < \infty$ ): Decidable in polynomial time by testing for cycles in the non-terminal dependency graph that can generate terminal substrings. Hence option D is decidable.
Undecidable Property of CFGs:
- Ambiguity problem: Determining whether an arbitrary context-free grammar $G$ is ambiguous (generates at least one string with two or more distinct parse trees) is undecidable.
- This is established via reduction from the Post Correspondence Problem (PCP).

Therefore, the undecidable problem is deciding if a given CFG is ambiguous (option A).

Final answer

Common trap

Assuming CFG ambiguity is decidable like emptiness or finiteness.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.