The GATE Grind

GATE 2021 CS – Question 22

Theory of Computation · Turing Machines and Undecidability · 1 mark · Multiple select

Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are NOT recursive?

  1. $L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \emptyset\}$
  2. $L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \Sigma^*\}$
  3. $L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \emptyset\}$
  4. $L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \Sigma^*\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \Sigma^*\}$

Explanation

Emptiness and universality are decidable for DFAs, and emptiness is decidable for PDAs. Universality of PDAs (CFGs) is undecidable, so only D is not recursive.