GATE PYQ

Recursive Language

Q1.
The set of all recursively enumerable languages is

Q2.
Let < M > denote an encoding of an automaton M. Suppose that \Sigma =\{0,1\}. Which of the following languages is/are NOT recursive?

Q3.
If L and P are two recursively enumerable languages then they are not closed under

Q4.
Given the following statementsS1 : Every context-sensitive language L is recursiveS2 : There exists a recursive language that is not context-sensitiveWhich statements are true?

Q5.
Which of the following statements is/are TRUE? MSQ

Q6.
Let L be a language and \bar{L} be its complement. Which of the following is NOT a viable possibility?

Q7.
A problem whose language is recursion is called?

Q8.
If L and \bar L are recursively enumerable then L is

Q9.
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?

Q10.
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?