NEW
New Website Launch
Experience the best way to solve previous year questions with mock tests (very detailed analysis), bookmark your favourite questions, practice etc...
VISIT NOW

GATE CSE

Recursively Enumerable Language and Turing Machine

Theory of Computation

Previous Years Questions

Marks 1

More
Which of the following is/are undecidable?
GATE CSE 2022
Which of the following statements is/are TRUE?
GATE CSE 2022
Consider the following types of languages: $${L_1}:$$ Regular, $${L_2}:$$ Context-free, $${L_3}:$$ Recursive, $${L_4}:$$...
GATE CSE 2016 Set 2
Consider the following statements. $$\,\,\,$$ $${\rm I}.\,\,\,\,\,\,\,\,\,$$ The complement of every Turing decidable la...
GATE CSE 2015 Set 2
For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which o...
GATE CSE 2015 Set 1
Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to la...
GATE CSE 2014 Set 2
Which of the following statements is/are FALSE? $$1.$$ For every non-deterministic Turing machine, there exists an equiv...
GATE CSE 2013
Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$...
GATE CSE 2008
If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which ...
GATE CSE 2003
Nobody knows yet if $$P=NP$$. Consider the language $$L$$ defined as follows $$L = \left\{ {\matrix{ {{{\left( {0 + 1...
GATE CSE 2003
Regarding the power of recognition of languages, which of the following statement is false?
GATE CSE 1998
Which of the following statements is / are true / false? Regular languages are closed under infinite union.
GATE CSE 1992
Which of the following statements is / are true / false? Union of two recursive languages is recursive
GATE CSE 1992
Which of the following statements is / are true / false? The language $$\left\{ {{0^n}\,\left| {\,n} \right.} \right.$$ ...
GATE CSE 1992

Marks 2

More
For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages. L1 = {(M) | M takes more th...
GATE CSE 2021 Set 1
Consider the following problems. $$L(G)$$ denotes the language generated by a grammar $$G.$$ $$L(M)$$ denotes the langua...
GATE CSE 2018
The set of all recursively enumerable languages is
GATE CSE 2018
Consider the following languages. $$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_1} = \left\{ {\left\langle M \right\rangle |M} \righ...
GATE CSE 2016 Set 2
Let $$X$$ be a recursive language and $$Y$$ be a recursively enumerable but not recursive language. Let $$W$$ and $$Z$$ ...
GATE CSE 2016 Set 1
Let $$L$$ be a language and $$\overline L $$ be its complement. Which one of the following is NOT a viable possibility?
GATE CSE 2014 Set 1
Let $$ < M > $$ be the encoding of a Turing machine as a string over $$\sum { = \left\{ {0,1} \right\}.} $$ Let $...
GATE CSE 2014 Set 2
If $$L$$ and $$\overline L $$ are recursively enumerable then $$L$$ is
GATE CSE 2008
Let $${L_1}$$ be a regular language, $${L_2}$$ be a deterministic context-free language and $${L_3}$$ a recursively enum...
GATE CSE 2006
For $$s \in {\left( {0 + 1} \right)^ * },$$ let $$d(s)$$ denote the decimal value of $$s(e. g.d(101)=5)$$ Let $$L = \lef...
GATE CSE 2006
Let $${L_1}$$ be a recursive language, and Let $${L_2}$$ be a recursively enumerable but not a recursive language. Which...
GATE CSE 2005
Define Languages $${L_0}$$ and $${L_1}$$ as follows $${L_0} = \left\{ { < M,\,w,\,0 > \left| {M\,\,} \right.} \rig...
GATE CSE 2003
A single tape Turing Machine $$M$$ has two states $${q_0}$$ and $${q_1}$$, of which $${q_0}$$ is the starting state. The...
GATE CSE 2003
The $$C$$ language is:
GATE CSE 2002
Which of the following is true?
GATE CSE 2002
Which one of the following is not decidable?
GATE CSE 1997
Which of the following conversions is not possible (algorithmically)?
GATE CSE 1994
In which of the cases stated below is the following statement true? “For every non-deterministic machine $${M_1}$$ there...
GATE CSE 1992
Recursive languages are:
GATE CSE 1990

Joint Entrance Examination

JEE Main JEE Advanced WB JEE

Graduate Aptitude Test in Engineering

GATE CSE GATE ECE GATE EE GATE ME GATE CE GATE PI GATE IN

Medical

NEET

CBSE

Class 12