GATE CS 2021 (Forenoon) — Question 22

Theory of Computation (TOC)Turing Machines & UndecidabilityMSQ1 markMedium

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. A
    \(L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \phi\}\)
  2. B
    \(L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \Sigma^*\}\)
  3. C
    \(L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \phi\}\)
  4. D
    \(L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \Sigma^*\}\)
Practise the full 2021-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAThis week's 10-question challengeSame 10 past-GATE questions for everyone this week — see where you stand.
Practise more on Turing Machines & UndecidabilityTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group