GATE CS 2018 Set 1 — Question 46

Let's analyze each problem:(I) For an unrestricted grammar $G$ and a string $w$, whether $w \in L(G)$
This is the Membership Problem for recursively enumerable languages. Unrestricted grammars generate recursively enumerable languages. This problem is equivalent to the Halting Problem and is Undecidable.(II) Given a Turing machine $M$, whether L(M) is regular
This asks if the language accepted by a TM has the property of being regular. Regularity is a non-trivial property of recursively enumerable languages. By Rice's Theorem, any non-trivial property of RE languages is Undecidable.(III) Given two grammars $G_1$ and $G_2$, whether $L(G_1) = L(G_2)$
This is the Equivalence Problem. The term "grammar" without qualification typically refers to Context-Free Grammars (Type-2) or Unrestricted Grammars (Type-0) in this context. The equivalence problem is undecidable for Context-Free Grammars and, by extension, for Unrestricted Grammars. Thus, it is Undecidable.(IV) Given an NFA $N$, whether there is a deterministic PDA $P$ such that $N$ and $P$ accept the same language.
An NFA $N$ accepts a regular language L(N). The class of regular languages is a proper subset of Deterministic Context-Free Languages (DCFLs), which are accepted by Deterministic Pushdown Automata (DPDAs). Therefore, for every regular language (and thus for every NFA), there exists a DPDA that accepts it. The answer to this problem is always "Yes". Since the answer is constant and trivial, the problem is Decidable.Conclusion:
Statements I, II, and III are undecidable. Statement IV is decidable.Therefore, option (D) is correct.