GATE CS 2016 Set 1 Q17 — Undecidability

We analyze the decidability of each decision problem:

1. Given NFAs $N_1$ and $N_2$, is $L(N_1) \cap L(N_2) = \emptyset$?
   Decidable. Regular languages are closed under intersection, and the resulting intersection language can be represented by a product DFA/NFA. The emptiness of a regular language is decidable (by checking reachability of any final state from the start state in the transition graph).
2. Given a CFG $G$ and a string $x \in \Sigma^*$, does $x \in L(G)$?
   Decidable. This is the membership problem for Context-Free Grammars, which can be solved in polynomial time using parsing algorithms like the CYK algorithm.
3. Given CFGs $G_1$ and $G_2$, is $L(G_1) = L(G_2)$?
   Undecidable. The equivalence problem for context-free languages is a well-known undecidable problem.
4. Given a TM $M$, is $L(M) = \emptyset$?
   Undecidable. The emptiness problem for Turing Machines is undecidable, which can be shown via reduction from the Halting Problem or by Rice's Theorem (as emptiness is a non-trivial semantic property of recursively enumerable languages).

Thus, problems III and IV are undecidable, making C the correct option.