Recursive Language


Question 1
Which of the following statements is/are TRUE?
MSQ
A
Every subset of a recursively enumerable language is recursive.
B
If a language L and its complement \bar{L} are both recursively enumerable, then L must be recursive.
C
Complement of a context-free language must be recursive.
D
If L_1 and L_2 are regular, then L_1 \cap L_2 must be deterministic context-free.
GATE CSE 2022   Theory of Computation
Question 2
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 3
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 4
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 5
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


There are 5 questions to complete.

Leave a Comment