GATE 2018 CS Q.36: solution and answer

GATE 2018 · CSQ.36 · 2 marks · MCQ

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?

(A)
Only I and II are undecidable
(B)
Only III is undecidable
(C)
Only II and IV are undecidable
(D)
Only I, II and III are undecidable

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option D: only I, II and III are undecidable; IV is decidable because its answer is always yes.

Official answer: DSource: Official answer key, GATE 2018 CS (IIT Guwahati)

(I) Type-0 (unrestricted) grammars generate exactly the recursively enumerable languages. Deciding whether $w \in L (G)$ would decide whether a Turing machine accepts $w$ , which is the acceptance (halting) problem. So (I) is undecidable.
(II) "Is $L (M)$ regular?" is a property of the language of a Turing machine. It is non-trivial: $L (M) = \emptyset$ is regular, while $L (M) = {0^{n} 1^{n} ∣ n \geq 0}$ is not. By Rice's theorem, a non-trivial property of recursively enumerable languages is undecidable. So (II) is undecidable.
(III) Equivalence $L (G_{1}) = L (G_{2})$ is undecidable already when $G_{1}$ and $G_{2}$ are context-free grammars. A context-free grammar is a grammar, so a decision procedure for arbitrary grammars would also decide it for context-free grammars. So (III) is undecidable.
(IV) Every NFA accepts a regular language. Every regular language is accepted by a deterministic PDA, namely a DFA that never uses its stack. So for every NFA $N$ a suitable $P$ exists and the answer is always yes. A procedure that always outputs yes is a decision procedure, so (IV) is decidable.
Undecidable: (I), (II), (III). Decidable: (IV). This is option (D).

KEY IDEA

Membership for type-0 grammars, regularity of a Turing machine's language (Rice) and grammar equivalence are undecidable. The NFA-to-DPDA question is trivially decidable, since every regular language has a DPDA.

WATCH OUT FOR

Treating (IV) as hard because it mentions a deterministic PDA. Deterministic PDAs are strictly weaker than nondeterministic ones, but every regular language still has a DPDA, so the answer is always yes. Another slip is calling (II) decidable because regular languages look simple, when Rice's theorem applies to the TM's language.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 8 Turing machines questions, with notes

GATE 2018 CS Q.36: solution and answer

Answer and solution

More Turing machines questions