# Recursively Enumerable Language and Turing Machine · Theory of Computation · GATE CSE

Start Practice## Marks 1

GATE CSE 2022

Which of the following statements is/are TRUE?

GATE CSE 2022

Which of the following is/are undecidable?

GATE CSE 2016 Set 2

Consider the following types of languages: $${L_1}:$$ Regular, $${L_2}:$$ Context-free, $${L_3}:$$ Recursive, $${L_4}:$$ Recursively enumerable. Which...

GATE CSE 2015 Set 1

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessa...

GATE CSE 2015 Set 2

Consider the following statements.
$$\,\,\,$$ $${\rm I}.\,\,\,\,\,\,\,\,\,$$ The complement of every Turing decidable language is Turing decidable
$$\...

GATE CSE 2014 Set 2

Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the...

GATE CSE 2013

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

GATE CSE 2008

Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?

GATE CSE 2003

Nobody knows yet if $$P=NP$$. Consider the language $$L$$ defined as follows
$$L = \left\{ {\matrix{
{{{\left( {0 + 1} \right)}^ * }\,\,\,if\,\,P =...

GATE CSE 2003

If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which of the following statements is...

GATE CSE 1998

Regarding the power of recognition of languages, which of the following statement is false?

GATE CSE 1992

Which of the following statements is / are true / false?
The language $$\left\{ {{0^n}\,\left| {\,n} \right.} \right.$$ is prime$$\left. \, \right\}$$...

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?
Regular languages are closed under infinite union.

## Marks 2

GATE CSE 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 steps on all inputs}
...

GATE CSE 2018

The set of all recursively enumerable languages is

GATE CSE 2018

Consider the following problems. $$L(G)$$ denotes the language generated by a grammar $$G.$$ $$L(M)$$ denotes the language accepted by a machine $$M.$...

GATE CSE 2016 Set 2

Consider the following languages.
$$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_1} = \left\{ {\left\langle M \right\rangle |M} \right.$$ takes at least $$2016$$ s...

GATE CSE 2016 Set 1

Let $$X$$ be a recursive language and $$Y$$ be a recursively enumerable but not recursive language. Let $$W$$ and $$Z$$ be two languages such that $$\...

GATE CSE 2014 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 2

Let $$ < M > $$ be the encoding of a Turing machine as a string over $$\sum { = \left\{ {0,1} \right\}.} $$
Let $$L = \left\{ { < M > \le...

GATE CSE 2008

If $$L$$ and $$\overline L $$ are recursively enumerable then $$L$$ is

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 = \left\{ {s \in {{\left( {0 + 1} \r...

GATE CSE 2006

Let $${L_1}$$ be a regular language, $${L_2}$$ be a deterministic context-free language and $${L_3}$$ a recursively enumerable, but not recursive, lan...

GATE CSE 2005

Let $${L_1}$$ be a recursive language, and Let $${L_2}$$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

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 tape alphabet of $$M$$ is $$\...

GATE CSE 2003

Define Languages $${L_0}$$ and $${L_1}$$ as follows
$${L_0} = \left\{ { < M,\,w,\,0 > \left| {M\,\,} \right.} \right.$$ halts on $$\left. w \rig...

GATE CSE 2002

Which of the following is true?

GATE CSE 2002

The $$C$$ language is:

GATE CSE 1997

Which one of the following is not decidable?

GATE CSE 1994

Which of the following conversions is not possible (algorithmically)?

GATE CSE 1992

In which of the cases stated below is the following statement true?
“For every non-deterministic machine $${M_1}$$ there exists an equivalent determin...

GATE CSE 1990

Recursive languages are: