GATE CS 2018 Q.46 (CS Q.36): Decidability, Reducibility and 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$ .

(I) For an unrestricted grammar $G$ and a string $w$ , whether $w \in L(G)$
(II) Given a Turing machine $M$ , whether $L(M)$ is regular
(III) Given two grammars $G_1$ and $G_2$ , whether $L(G_1) = L(G_2)$
(IV) 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 statements is correct?

Only I and II are undecidable

Only III is undecidable

Only II and IV are undecidable

Only I, II and III are undecidable

Official answer and solution

Official answer: D
From: Official GATE 2018 answer key

Solution

Classify decidability for membership, semantic regularity, language equivalence, and DCFL containment of regular languages.

Analyze the four problems:

Problem I: For an unrestricted grammar $G$ , $L(G)$ is a recursively enumerable language (Type 0). The membership problem ( $w \in L(G)$ ) is undecidable (equivalent to Turing machine halting/acceptance problem).
Problem II: Deciding whether $L(M)$ of an arbitrary Turing machine is regular is a non-trivial semantic language property. By Rice's Theorem, this problem is undecidable.
Problem III: The language equivalence problem ( $L(G_1) = L(G_2)$ ) is undecidable for context-free grammars, and therefore undecidable for unrestricted grammars.
Problem IV: $N$ is an NFA, so $L(N)$ is a regular language. Every regular language is a deterministic context-free language (DCFL) and can be accepted by a deterministic PDA. Therefore, for every NFA $N$ , such a DPDA $P$ always exists. Since the answer is always YES for any input, the problem is decidable.

Therefore, only problems I, II, and III are undecidable, matching option D.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 46 of 65, printed as CS Q.36
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source