1

### GATE CSE 2016 Set 2

Consider the following languages: \eqalign{ & {L_1} = \left\{ {{a^n}{b^m}{c^{n + m}}:m,n \ge 1} \right\} \cr & {L_2} = \left\{ {{a^n}{b^n}{c^{2n}}:n \ge 1} \right\} \cr}

Which one of the following is TRUE?

A
Both ${L_1}$ and ${L_2}$ are context-free.
B
${L_1}$ is context-free while ${L_2}$ is not context-free.
C
${L_2}$ is context-free while ${L_1}$ is not context-free.
D
Neither ${L_1}$ nor ${L_2}$ is context-free.
2

### 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
3

### 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
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