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 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 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 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 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 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 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 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 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 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
There are 10 questions to complete.

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.