GATE CS 2013 Q41 — Undecidability

To determine which of the given problems are undecidable, let us analyze each statement individually:

1. $G$ is a CFG. Is $L(G) = \phi$? (Emptiness Problem)
   This is decidable. We can determine if a Context-Free Grammar (CFG) is empty by checking if the start symbol can derive any terminal string. This is done using a bottom-up marking algorithm to find all "generating" variables. If the start symbol is generating, the language is non-empty; otherwise, it is empty.


2. $G$ is a CFG. Is $L(G) = \Sigma^*$? (Universality Problem)
   This is undecidable. The problem of checking whether a CFG generates all possible strings over its alphabet is undecidable, which can be shown by reducing the Turing machine halting problem (via valid computation histories) to it.


3. $M$ is a Turing machine. Is $L(M)$ regular? (Regularity Problem)
   This is undecidable. According to Rice's Theorem, any non-trivial semantic property of recursively enumerable languages (languages recognized by Turing machines) is undecidable. Since "being regular" is a semantic property of the language, and it is non-trivial (some TMs accept regular languages, while others do not), this problem is undecidable.


4. $A$ is a DFA and $N$ is an NFA. Is $L(A) = L(N)$? (Equivalence Problem)
   This is decidable. Regular languages are closed under complementation, intersection, and union. We can construct a DFA for the symmetric difference $(L(A) \cap \overline{L(N)}) \cup (\overline{L(A)} \cap L(N))$ and test if this resulting language is empty, which is a decidable property.

Thus, only statements 2 and 3 are undecidable.

Correct Option: D