Turing Machine: RE, REC and Undecidability GATE 2021 Question #619 with Solution

GATE 2021 · Set-1

Theory of ComputationTuring Machine: RE, REC and UndecidabilitymediumMSQ1 mark

Let <M> denote an encoding of an automaton M. Suppose that Σ = {0,1}. Which of the following languages is/are NOT recursive?

AL = {<M> | M is a DFA such that L(M) = {}}BL = {<M> | M is a DFA such that L(M) = Σ*}CL = {<M> | M is a PDA such that L(M) = {}}DL = {<M> | M is a PDA such that L(M) = Σ*}

Select every correct option.

Save your progress

Related Theory of Computation PYQs

GATE 2021 · Set-1

Suppose that L1 is a regular language and L2 is a context-free language. Which one of the following languages is NOT necessarily c…

GATE 2021 · Set-1

For a Turing machine M, <M> denotes an encoding of M. Consider the following two languages. L1 = {<M> | M takes more than 2021 ste…

GATE 2021 · Set-1

The number of strings of length 100 accepted by the below pushdown automaton is _______________.

GATE 2021 · Set-2

Let L be a subset of {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following l…

GATE 2021 · Set-2

Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?

GATE 2021 · Set-2

Consider the following two statements about regular languages: S1: Every infinite regular language contains an undecidable languag…

Saved progressKeep answers, mock results and completion history across devices.

Adaptive practiceGet questions matched to your recent accuracy and difficulty level.

Bookmarks and notesBuild a personal revision list and record why a question was difficult.

Performance insightsSee weak subjects, accuracy trends, streaks and exam readiness.

Related Theory of Computation PYQs

Turn practice into measurable progress