Turing Machine: RE, REC and Undecidability GATE 2008 Question #2744 with Solution

GATE 2008

Theory of ComputationTuring Machine: RE, REC and UndecidabilitymediumMCQ2 marks

Which of the following statements is false?

AEvery NFA can be converted to an equivalent DFABEvery non-deterministic Turing machine can be converted to an equivalent deterministic Turing machineCEvery regular language is also a context-free languageDEvery subset of a recursively enumerable set is recursive GATE CSE – 2015 SET-1 MCQ (2-MARKS) GATE CSE – 2014 SET-2 MCQ (2-MARKS) GATE CSE – 2014 SET-2 MCQ (1-MARKS) GATE CSE – 2014 SET-3 MCQ (1-MARKS) GATE CSE – 2013 MCQ (2-MARKS) GATE CSE – 2013 MCQ (2-MARKS) GATE CSE – 2009 MCQ (2-MARKS) GATE CSE – 2008 MCQ (2-MARKS) 240 THEORY OF COMPUTATION Check Out Our GATE Courses & Secure Your Dream Rank!

Save your progress

Related Theory of Computation PYQs

GATE 2008

Which of the following is true for the language { ap | p is prime} ?

GATE 2008

Let L be a regular language. Which of the following operations is NOT closed for regular languages?

GATE 2008

The language L = {<M> | M is a Turing Machine that accepts the string 'gate'} is:

GATE 2008

Which of the following pairs of regular expressions are NOT equivalent?

GATE 2008

Which of the following problems on Turing machines is decidable?

GATE 2008

Which of the following statements about regular expressions and finite automata is FALSE?

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