1
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+2
-0.6
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
MCQ (Single Correct Answer)
+1
-0.3
Consider the following types of languages: $${L_1}:$$ Regular, $${L_2}:$$ Context-free, $${L_3}:$$ Recursive, $${L_4}:$$ Recursively enumerable. Which of the following is/are TRUE?

$$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ $$\overline {{L_3}} \cup {L_4}$$ is recursively enumerable
$$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ $$\overline {{L_2}} \cup {L_3}$$ is recursive
$$\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ $$L_1^ * \cap {L_2}$$ is context-free
$$\,\,\,{\rm I}V.\,\,\,\,\,\,\,$$ $${L_1} \cup \overline {{L_2}} $$ is context-free

A
$${\rm I}$$ only
B
$${\rm I}$$ and $${\rm III}$$ only
C
$${\rm I}$$ and $${\rm IV}$$ only
D
$${\rm I},$$ $${\rm II}$$ and $${\rm III}$$ only
3
GATE CSE 2016 Set 2
Numerical
+1
-0
The number of states in the minimum sized $$DFA$$ that accepts the language defined by the regular expression $$${\left( {0 + 1} \right)^ * }\left( {0 + 1} \right){\left( {0 + 1} \right)^ * }$$$
is ___________________.
Your input ____
4
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+1
-0.3
Computers were invented for performing only high-end useful computations. However, it is no understatement that they have taken over our world today. The internet, for example, is ubiquitous. Many believe that the internet itself is an unintended consequence of the original invention. With the advent of mobile computing on our phones, a whole new dimension is now enabled. One is left wondering if all these developments are good or, more importantly, required.

Which of the statement(s) below is/are logically valid and can be inferred from the above paragraph?

$$\,\,\,\,\,\,\,\,\,$$$$(i)$$ $$\,\,\,\,\,\,\,\,\,$$ The author believes that computers are not good for us.
$$\,\,\,\,\,\,\,$$ $$(ii)$$ $$\,\,\,\,\,\,\,\,\,$$ Mobile computers and the internet are both intended inventions

A
$$(i)$$ only
B
$$(ii)$$ only
C
both $$(i)$$ and $$(ii)$$ only
D
neither $$(i)$$ nor $$(ii)$$