1
GATE CSE 2016 Set 1
+2
-0.6
Let $$X$$ be a recursive language and $$Y$$ be a recursively enumerable but not recursive language. Let $$W$$ and $$Z$$ be two languages such that $$\overline Y$$ reduces to $$W,$$ and $$Z$$ reduces to $$\overline X$$ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?
A
$$W$$ can be recursively enumerable and $$Z$$ is recursive.
B
$$W$$ can be recursive and $$Z$$ is recursively enumerable.
C
$$W$$ is not recursively enumerable and $$Z$$ is recursive.
D
$$W$$ is not recursively enumerable and $$Z$$ is not recursive.
2
GATE CSE 2014 Set 2
+2
-0.6
Let $$< M >$$ be the encoding of a Turing machine as a string over $$\sum { = \left\{ {0,1} \right\}.}$$
Let $$L = \left\{ { < M > \left| M \right.} \right.$$ is a Turing machine that accepts a string of length $$\left. {2014} \right\}.$$ Then, $$L$$ is
A
decidable and recursively enumerable
B
un-decidable but recursively enumerable
C
un-decidable and not recursively enumerable
D
decidable but not recursively enumerable
3
GATE CSE 2014 Set 1
+2
-0.6
Let $$L$$ be a language and $$\overline L$$ be its complement. Which one of the following is NOT a viable possibility?
A
Neither $$L$$ nor $$\overline L$$ is recursively enumerable (r.e).
B
One of $$L$$ and $$\overline L$$ is r.e. but not recursive; the other is not r.e.
C
Both $$L$$ and $$\overline L$$ are r.e. but not recursive.
D
Both $$L$$ and $$\overline L$$ are recursive.
4
GATE CSE 2008
+2
-0.6
If $$L$$ and $$\overline L$$ are recursively enumerable then $$L$$ is
A
Regular
B
Context-free
C
Context-sensitive
D
Recursive.
GATE CSE Subjects
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
EXAM MAP
Joint Entrance Examination