Let denote the encoding of a Turing machine M. The language L = { | L(M) contains at least 10 strings} is:

Turing Machine: RE, REC and Undecidability GATE 2014 Question #7766 with Solution

GATE 2014 · SET - 1

Theory of ComputationTuring Machine: RE, REC and UndecidabilitymediumMCQ2 marks

Let <M> denote the encoding of a Turing machine M. The language L = {<M> | L(M) contains at least 10 strings} is:

ARecursiveBRecursively Enumerable but not RecursiveCNot Recursively EnumerableDRegular

Let <M> be the encoding of a Turing Machine as a string over Σ = {0,1}. Let L = {<M> | M is a Turing Machine that accepts a string…

Let Σ be a finite non-empty alphabet and let 2^(Σ*) be the power set of Σ*. Which of the following is TRUE?

Which of the following decision problems regarding formal languages is UNDECIDABLE?

Let <M> be the encoding of a Turing machine as a string over Σ = {0, 1} Let L = { <M> |M is a Turing machine that accepts a string…

Let A≤mB denotes that language A is mapping reducible (also known as many-to-one reducible) to language B.Which one of the followi…

Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ*. Which one of the following is TRUE?

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.