1
GATE CSE 2014 Set 2
MCQ (Single Correct Answer)
+1
-0.3
Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the following is FALSE?
A
If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is recursive then $$A$$ is recursive.
B
If $$A\,\,{ \le _m}\,\,B$$ and $$A$$ is undecidable then $$B$$ is un-decidable.
C
If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is recursively enumerable then $$A$$ is recursively enumerable.
D
If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is not recursively enumerable then $$A$$ is not recursively enumerable.
2
GATE CSE 2013
MCQ (Single Correct Answer)
+1
-0.3
Which of the following statements is/are FALSE?
$$1.$$ For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine
$$2.$$ Turing recognizable languages are closed under union and complementation
$$3.$$ Turing decidable languages are closed under intersection and complementation
$$4.$$ Turing recognizable languages are closed under union and intersection
A
$$1$$ and $$4$$ only
B
$$1$$ and $$3$$ only
C
$$2$$ only
D
$$3$$ only
3
GATE CSE 2008
MCQ (Single Correct Answer)
+1
-0.3
Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?
A
It is not accepted by a Turing machine
B
It is regular but not context-free
C
It is context-free but not regular
D
It is neither regular nor context-free, but accepted by a Turing machine
4
GATE CSE 2003
MCQ (Single Correct Answer)
+1
-0.3
Nobody knows yet if $$P=NP$$. Consider the language $$L$$ defined as follows
$$L = \left\{ {\matrix{ {{{\left( {0 + 1} \right)}^ * }\,\,\,if\,\,P = NP} \cr {\,\,\,\,\,\,\,\phi \,\,\,\,Otherwise} \cr } } \right.$$

Which of the following statement is true?

A
$$L$$ is recursive
B
$$L$$ is recursively enumerable but not recursive
C
$$L$$ is not recursively enumerable
D
Whether $$L$$ is recursive or not will be known after we find out if $$P=NP.$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12