The GATE Grind

GATE 2018 CS – Question 46

Theory of Computation · Turing Machines and Undecidability · 2 marks · Multiple choice

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?

  1. Only I and II are undecidable
  2. Only III is undecidable
  3. Only II and IV are undecidable
  4. Only I, II and III are undecidable

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) Only I, II and III are undecidable

Explanation

Membership for unrestricted grammars is undecidable (I), regularity of a Turing machine's language is undecidable by Rice's theorem (II), and equivalence of grammars is undecidable (III). Problem IV is trivially decidable, since every regular language is accepted by some deterministic PDA, so the answer is always yes.