GATE 2016 CS – Question 27
Which of the following decision problems are undecidable?
I. Given NFAs $N_1$ and $N_2$, is $L(N_1) \cap L(N_2) = \Phi$?
II. Given a CFG $G = (N, \Sigma, P, S)$ and a string $x \in \Sigma^*$, does $x \in L(G)$?
III. Given CFGs $G_1$ and $G_2$, is $L(G_1) = L(G_2)$?
IV. Given a TM $M$, is $L(M) = \Phi$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) III and IV only
Explanation
Problem I is decidable, since the intersection of two regular languages is regular and its emptiness can be checked. Problem II is decidable with the CYK algorithm. Equivalence of two context-free grammars (III) is undecidable, and emptiness of a Turing machine's language (IV) is undecidable by Rice's theorem.