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

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

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

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

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

NEET

Class 12