The GATE Grind

GATE 2014 CS (CS3) – Question 45

Theory of Computation · Turing Machines and Undecidability · 2 marks · Multiple choice

Which problem is undecidable?

  1. Whether a given context-free grammar is ambiguous
  2. Whether a given string is generated by a given context-free grammar
  3. Whether the language of a given context-free grammar is empty
  4. Whether the language of a given context-free grammar is finite

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Whether a given context-free grammar is ambiguous

Explanation

General context-free grammar ambiguity is undecidable: no algorithm decides ambiguity for every CFG. Therefore **A**. Membership is decidable by parsing, while emptiness and finiteness can be decided using productive/reachable symbols and cycles in the grammar.