1
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+2
-0.67

For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages.

L1 = {(M) | M takes more than 2021 steps on all inputs}

L2 = {(M) | M takes more than 2021 steps on some input}

Which one of the following options is correct?

A
Both L1 and L2 are undecidable.
B
L1 is undecidable and L2 is decidable.
C
L1 is decidable and L2 is undecidable.
D
Both L1 and L2 are decidable.
2
GATE CSE 2018
MCQ (Single Correct Answer)
+2
-0.6
The set of all recursively enumerable languages is
A
closed under complementation.
B
closed under intersection.
C
a subset of the set of all recursive languages
D
an uncountable set.
3
GATE CSE 2018
MCQ (Single Correct Answer)
+2
-0.6
Consider the following problems. $$L(G)$$ denotes the language generated by a grammar $$G.$$ $$L(M)$$ denotes the language accepted by a machine $$M.$$

$$\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ For an unrestricted grammar $$G$$ and a string $$W,$$ whether $$w \in L\left( G \right)$$
$$\,\,\,\,\,\,{\rm II}.\,\,\,\,\,\,\,$$ Given a Turing machine $$M,$$ whether $$L(M)$$ is regular
$$\,\,\,\,{\rm III}.\,\,\,\,\,\,\,$$ Given two grammars $${G_1}$$ and $${G_2}$$, whether $$L\left( {{G_1}} \right) = L\left( {{G_2}} \right)$$
$$\,\,\,\,{\rm IV}.\,\,\,\,\,\,\,$$ Given an $$NFA$$ $$N,$$ whether there is a deterministic $$PDA$$ $$P$$ such that $$N$$
$$\,\,\,\,\,\,\,\,\,\,\,\,\,$$ $$\,\,\,\,\,\,\,\\,\,\,$$and $$P$$ accept the same language.

Which one of the following statements is correct?

A
Only $${\rm I}$$ and $${\rm I}$$$${\rm I}$$ are undecidable
B
Only $${\rm III}$$ is undecidable
C
Only $${\rm I}$$$${\rm I}$$ and $${\rm IV}$$ are undecidable
D
Only $${\rm I}$$, $${\rm II}$$ and $${\rm III}$$ are undecidable
4
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
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
CBSE
Class 12