Question 41

Let us examine each statement:

1. $G$ is a CFG. Is $L(G) = \Phi$?
   This is the emptiness problem for context-free grammars. We can determine generating non-terminals in polynomial time and check whether the start symbol can derive any string of terminals. Hence, this problem is decidable.

2. $G$ is a CFG. Is $L(G) = \Sigma^*$?
   This is the universality problem for context-free grammars. It is known to be undecidable (by reduction from the Post Correspondence Problem or valid computation histories of Turing machines).

3. $M$ is a Turing machine. Is $L(M)$ regular?
   By Rice's Theorem, any non-trivial semantic property of the language accepted by a Turing machine is undecidable. Since regularity is non-trivial (some Turing machines 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)$?
   We can convert the NFA $N$ to an equivalent DFA $N'$ using the subset construction, and then check whether the symmetric difference $(L(A) \cap \overline{L(N')}) \cup (\overline{L(A)} \cap L(N'))$ is empty. Since emptiness of regular languages is decidable, this equivalence problem is decidable.

Therefore, problems 2 and 3 are undecidable, which corresponds to option (D).