1

### GATE CSE 2015 Set 2

Consider the following statements.

$\,\,\,$ ${\rm I}.\,\,\,\,\,\,\,\,\,$ The complement of every Turing decidable language is Turing decidable
$\,$ ${\rm II}.\,\,\,\,\,\,\,\,\,$ There exists some language which is in $NP$ but is not Turing decidable
${\rm III}.\,\,\,\,\,\,\,\,\,$ If $L$ is a language in $NP,$ $L$ is Turing decidable

Which of the above statements is/are true?

A
Only {\rm I}$${\rm I} B Only {\rm III} C Only {\rm I} and {\rm II} D Only {\rm I} and {\rm III} 2 Numerical ### GATE CSE 2015 Set 2 The number of states in the minimal deterministic finite automaton corresponding to the regular expression {\left( {0 + 1} \right)^{\,\, * }}\left( {10} \right) is ________________. Your Input ________ ## Answer Correct Answer is 3 3 MCQ (Single Correct Answer) ### GATE CSE 2015 Set 2 Which of the following languages is/are regular? {L_1}:\left\{ {wx{w^R}|w,x\, \in \left\{ {a,b} \right\}{}^ * } \right. and \left. {\left| w \right|,\left| x \right| > 0} \right\},\,{w^R} is the reverse of string w {L_2}:\left\{ {{a^n}{b^m}\left| {m \ne n} \right.} \right. and m,n \ge \left. 0 \right\} {L_3}:\left\{ {{a^p}{b^q}{c^r}\left| {p,q,r \ge 0} \right.} \right\} A {L_1} and {L_3} only B {L_2} only C {L_2} and {L_3} only D {L_3} only 4 MCQ (Single Correct Answer) ### GATE CSE 2015 Set 2 Consider the alphabet \sum { = \left\{ {0,1} \right\},} the null/empty string \lambda and the sets of strings {X_0},\,{X_1}, and {X_2} generated by the corresponding non-terminals of a regular grammar. {X_0},\,\,{X_1},\, and {X_2} are related as follows.$$\eqalign{ & {X_0} = 1\,X{}_1 \cr & {X_1} = 0{X_1} + 1\,{X_2} \cr & {X_2} = 0\,{X_1} + \left\{ \lambda \right\} \cr}\$
Which one of the following choices precisely represents the strings in ${X_0}$?
A
$10\left( {{0^ * } + {{\left( {10} \right)}^ * }} \right)1$
B
$10\left( {{0^ * } + \left( {10} \right){}^ * } \right){}^ * 1$
C
$1\left( {0 + 10} \right){}^ * 1$
D
$10\left( {0 + 10} \right){}^ * 1 + 110\left( {0 + 10} \right){}^ * 1$

### Paper Analysis of GATE CSE 2015 Set 2

Subject NameTotal Questions
Algorithms5
Compiler Design3
Computer Networks6
Computer Organization4
Data Structures3
Database Management System4
Digital Logic3
Discrete Mathematics12
Operating Systems4
Programming Languages3
Software Engineering3
Theory of Computation4
Web Technologies1