1

### GATE CSE 2016 Set 2

Consider the following languages.

$\,\,\,\,\,\,\,\,\,\,\,\,$ ${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?
A
${L_1}$ is recursive and ${L_2},$${L_3} are not recursive B {L_2} is recursive and {L_1},$${L_3}$ are not recursive
C
${L_1},$${L_2} are recursive and {L_3} is not recursive D {L_{1,}}$${L_{2,}}$${L_{3}}$ are recursive
2

### GATE CSE 2016 Set 2

The man who is now Municipal Commissioner worked as ____________________.
A
the security guard at a university
B
a security guard at the university
C
a security guard at university
D
the security guard at the university
3

### GATE CSE 2016 Set 2

Nobody knows how the Indian cricket team is going to cope with the difficult and seamer-friendly wickets in Australia.

Choose the option which is closest in meaning to the underlined phrase in the above sentence.

A
put up with
B
put in with
C
put down to
D
put up against
4

### GATE CSE 2016 Set 2

Find the odd one in the following group of words

mock, deride, praise, jeer

A
mock
B
deride
C
praise
D
jeer

### Paper Analysis of GATE CSE 2016 Set 2

Subject NameTotal Questions
Algorithms5
Compiler Design3
Computer Networks6
Computer Organization6
Data Structures5
Database Management System4
Digital Logic3
Discrete Mathematics11
Operating Systems3
Theory of Computation6
General Aptitude10