Turing Machine: RE, REC and Undecidability GATE 2013 Question #10033 with Solution

GATE 2013 · session-1

Theory of ComputationTuring Machine: RE, REC and UndecidabilityeasyMCQ1 mark

Which of the following statements about complexity classes are TRUE? 1. The problem of determining whether there exists a cycle in an undirected graph is in P. 2. The problem of determining whether there exists a cycle in an undirected graph is in NP. 3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

A1, 2 and 3B1 and 2 onlyC2 and 3 onlyD1 and 3 only

Save your progress

Related Theory of Computation PYQs

GATE 2013

Which of the following is/are undecidable? 1. G is a CFG. Is L(G) = ϕ? 2. G is a CFG. Is L(G) = Σ*? 3. M is a Turing machine. Is L…

GATE 2013

Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent determin…

GATE 2013

Which of the following languages is NOT regular?

GATE 2013

Which of the following statements is FALSE?

GATE 2013

Consider the following deterministic finite automaton (DFA) over the alphabet {0, 1} with states {q0, q1, q2}, where q0 is the sta…

GATE 2013

The language L = {a^n b^m c^m d^n | n, m >= 1} is:

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