1

### GATE CSE 2016 Set 2

Consider the following two statements:

$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$ If all states of an $NFA$ are accepting states then the language accepted by the
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ $NFA$ is $\sum {^ * } .$
$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,$ There exists a regular language $A$ such that for all languages $B,A \cap B$ is
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ regular.

Which one of the following is CORRECT?

A
Only ${\rm I}$ is true
B
Only ${\rm II}$ is true
C
Both ${\rm I}$ and ${\rm II}$ are true
D
Both ${\rm I}$ and ${\rm II}$ are false
2

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

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

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

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