NEW
New Website Launch
Experience the best way to solve previous year questions with mock tests (very detailed analysis), bookmark your favourite questions, practice etc...
1

GATE CSE 2014 Set 2

MCQ (Single Correct Answer)
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)
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)
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)
If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which of the following statements is true?
A
$$L$$ is necessarily finite
B
$$L$$ is regular but not necessarily finite
C
$$L$$ is context free but not necessarily regular
D
$$L$$ is recursive but not necessarily context free
Write for Us

Do you want to write for us? Help us by contributing to our platform.

Questions Asked from Recursively Enumerable Language and Turing Machine

On those following papers in Marks 1
Number in Brackets after Paper Indicates No. of Questions
GATE CSE 2022 (2)
GATE CSE 2016 Set 2 (1)
GATE CSE 2015 Set 1 (1)
GATE CSE 2015 Set 2 (1)
GATE CSE 2014 Set 2 (1)
GATE CSE 2013 (1)
GATE CSE 2008 (1)
GATE CSE 2003 (2)
GATE CSE 1998 (1)
GATE CSE 1992 (3)

Joint Entrance Examination

JEE Main JEE Advanced WB JEE

Graduate Aptitude Test in Engineering

GATE CSE GATE ECE GATE EE GATE ME GATE CE GATE PI GATE IN

Medical

NEET

CBSE

Class 12