Official PYQ · 2018Q36UndecidabilityMCQ2 marks

GATE CS 2018 Q36 — Undecidability

Consider the following problems. $L(G)$ denotes the language generated by a grammar $G$ . L(M) denotes the language accepted by a machine $M$ .

For an unrestricted grammar $G$ and a string $w$ , whether $w \in L(G)$
Given a Turing machine $M$ , whether $L(M)$ is regular
Given two grammar $G_1$ and $G_2$ , whether $L(G_1) = L(G_2)$
Given an NFA $N$ , whether there is a deterministic PDA $P$ such that $N$ and $P$ accept the same language

Which one of the following statement is correct?

View worked solution

Answer: D

Let us analyze the decidability of each problem:

Membership for Unrestricted Grammars: Unrestricted grammars generate Recursively Enumerable (RE) languages. The membership problem ( $w \in L(G)$ ) for RE languages is equivalent to the halting problem and is undecidable.
Regularity of Turing Machine Language: "Being regular" is a non-trivial semantic property of recursively enumerable languages. By Rice's Theorem, determining whether $L(M)$ is regular is undecidable.
Equivalence of Grammars: The equivalence problem ( $L(G_1) = L(G_2)$ ) is undecidable for both context-free grammars and unrestricted grammars.
NFA to DPDA Equivalence: Every regular language (accepted by an NFA $N$ ) is also a deterministic context-free language (DCFL), which can be accepted by a deterministic PDA $P$ . Therefore, for any given NFA $N$ , such a DPDA $P$ always exists. Since the answer is always "yes", this problem is trivially decidable.

Thus, only I, II, and III are undecidable.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Related questions