1

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

+2

-0.6

Consider the following languages.

where for each Turing machine $${M,\left\langle M \right\rangle }$$ denotes a specific encoding of $$M.$$ Which one of the following is

$$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_1} = \left\{ {\left\langle M \right\rangle |M} \right.$$ takes at least $$2016$$ steps on some input $$\left. \, \right\},$$

$$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_2} = \left\{ {\left\langle M \right\rangle |M} \right.$$ takes at least $$2016$$ steps on all inputs $$\left. \, \right\}$$ and

$$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_3} = \left\{ {\left\langle M \right\rangle |M} \right.$$ accepts $$\left. \varepsilon \right\},$$

where for each Turing machine $${M,\left\langle M \right\rangle }$$ denotes a specific encoding of $$M.$$ Which one of the following is

**TRUE**?2

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

+2

-0.6

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 $$\overline Y $$ reduces to $$W,$$ and $$Z$$ reduces to $$\overline X $$ (reduction means the standard many-one reduction). Which one of the following statements is

**TRUE**?3

GATE CSE 2014 Set 1

MCQ (Single Correct Answer)

+2

-0.6

Let $$L$$ be a language and $$\overline L $$ be its complement. Which one of the following is NOT a viable possibility?

4

GATE CSE 2014 Set 2

MCQ (Single Correct Answer)

+2

-0.6

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

Let $$L = \left\{ { < M > \left| M \right.} \right.$$ is a Turing machine that accepts a string of length $$\left. {2014} \right\}.$$ Then, $$L$$ is

Let $$L = \left\{ { < M > \left| M \right.} \right.$$ is a Turing machine that accepts a string of length $$\left. {2014} \right\}.$$ Then, $$L$$ is

Questions Asked from Recursively Enumerable Language and Turing Machine (Marks 2)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE Subjects

Discrete Mathematics

Programming Languages

Theory of Computation

Operating Systems

Computer Organization

Database Management System

Data Structures

Computer Networks

Algorithms

Compiler Design

Software Engineering

Web Technologies

General Aptitude