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?
$L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \emptyset\}$
$L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \Sigma^*\}$
$L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \emptyset\}$
$L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \Sigma^*\}$
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.
More Turing Machines and Undecidability questions
GATE 2021 CS (CS1) Q49– For a Turing machine M, M denotes an encoding of M. Consider the following two languages.…
GATE 2020 CS Q36– Which of the following languages are undecidable? Note that M indicates encoding of the…
GATE 2019 CS Q44– Consider the following sets: S1. Set of all recursively enumerable languages over the…
GATE 2018 CS Q17– The set of all recursively enumerable languages is
GATE 2018 CS Q46– Consider the following problems. L(G) denotes the language generated by a grammar G. L(M)…
GATE 2015 CS (CS1) Q28– For any two languages L 1 and L 2 such that L 1 is context-free and L 2 is recursively…