# Recursive Language

 Question 1
Let < M > denote an encoding of an automaton M. Suppose that $\Sigma =\{0,1\}$. Which of the following languages is/are NOT recursive?
 A $L= \{ \langle M \rangle \mid M \text{ is a DFA such that } L(M)=\emptyset \}$ B $L= \{ \langle M \rangle \mid M \text{ is a DFA such that } L(M)=\Sigma ^ * \}$ C $L= \{ \langle M \rangle \mid M \text{ is a PDA such that } L(M)=\emptyset \}$ D $L= \{ \langle M \rangle \mid M \text{ is a PDA such that } L(M)=\Sigma ^ * \}$
GATE CSE 2021 SET-1   Theory of Computation
Question 1 Explanation:
 Question 2
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
GATE CSE 2018   Theory of Computation
Question 2 Explanation:
 Question 3
If L and P are two recursively enumerable languages then they are not closed under
 A Kleene star $L^{*}$ of L B Intersection $L \cap P$ C Union $L \cup P$ D Set difference
ISRO CSE 2017   Theory of Computation
Question 3 Explanation:
 Question 4
Given the following statements
S1 : Every context-sensitive language L is recursive
S2 : There exists a recursive language that is not context-sensitive
Which statements are true?
 A Only S1 is correct B Only S2 is correct C Both S1 and S2 are not correct D Both S1 and S2 are correct
ISRO CSE 2017   Theory of Computation
Question 4 Explanation:
 Question 5
If $L$ and $\bar L$ are recursively enumerable then $L$ is
 A regular B context-free C context-sensitive D recursive
ISRO CSE 2016   Theory of Computation
Question 5 Explanation:
 Question 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 $\bar{Y}$ reduces to W, and Z reduces to $\bar{X}$ (reduction means the standard many-one-reduction). Which one of the following statements is TRUE?
 A W can berecursivelyenumerableand Z is recursive. B W can berecursiveand Z is recursivelyenumerable C W is notrecursivelyenumerableand Z is recursive D W is notrecursivelyenumerableand Z is notrecursive.
GATE CSE 2016 SET-1   Theory of Computation
Question 6 Explanation:
 Question 7
Let L be a language and $\bar{L}$ be its complement. Which of the following is NOT a viable possibility?
 A Neither L nor $\bar{L}$ is recursively enumerable (r.e.). B One of L and $\bar{L}$ is r.e. but not recursive; the other is not r.e. C Both L and $\bar{L}$ are r.e. but not recursive D Both L and $\bar{L}$ are recursive.
GATE CSE 2014 SET-1   Theory of Computation
Question 7 Explanation:
 Question 8
A problem whose language is recursion is called?
 A Unified problem B Boolean function C Recursive problem D Decidable
ISRO CSE 2011   Theory of Computation
Question 8 Explanation:
 Question 9
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
 A L2 - L1 is recursively enumerable B L1 - L3 is recursively enumerable C L2 $\cup$ L1 is recursively enumerable D L2 $\cap$ L1 is recursively enumerable
GATE CSE 2010   Theory of Computation
Question 9 Explanation:
 Question 10
If L and $\bar{L}$ are recursively enumerable then L is
 A regular B context-free C context-sensitive D recursive
GATE CSE 2008   Theory of Computation
Question 10 Explanation:
There are 10 questions to complete.