Previous Year Questions: Recursive Language

Q1: Which of the following statements is/are TRUE?  (2022)
(a) Every subset of a recursively enumerable language is recursive.
(b) If a language L and its complement are both recursively enumerable, then L must be recursive.
(c) Complement of a context-free language must be recursive.
(d) If L₁ and L₂ are regular, then L₁ ∩ L₂ must be deterministic context-free.
Ans: (b, c, d)
Sol: 
If a language and its complement is Recursively enumerable Then L is Recursive. It is the standard result And proof is also very easy.
So option B is true.
Complement of CFL must be Recursive. It is also True.
As we know the complement of CFL may or may not be CFL but it is bound to be Context sensitive language which means it is recursive As well.
So option C is also True.
Option D,
L₁ and L₂ both are Regular languages, so their intersection is also regular as regular language is closed under intersection.
Now Regular language is also deterministic context free language
so option D is also true.
Option A,
every subset of recursive enumerable language is Recursive.
This statement is false.
Counter example,
Say Sigma* is set of all strings which is an RE language.
Now every language is subset of sigma*.
Now any Recursively enumerable language is also subset of sigma* which is not recursive.

Q2: Let < M > denote an encoding of an automaton M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?  (2021 SET-1)
(a) L = {<M> | M is a DFA such that L (M) = ∅}
(b) L = {<M> | M is a DFA such that L (M) = ∑*}
(c) L = {<M> | M is a PDA such that L (M) = ∅}
(d) L = {<M> | M is a PDA such that L (M) = ∑*}
Ans: (d)
Sol: 
We can get minimal DFA for both A and B, as minimal DFAs for both of them are just single state DFAs,
And we know minimal DFA for any regular language is always unique. So they should be isomorphic to DFA_min (∅ ) and DFA_min (∑*) respectively.
It's easy to check if DFA_min for A is isomorphic to DFA_min (∅) as there's only 1 state, if they are isomorphic we say 'Yes', otherwise we say 'No'.
Same procedure can be applied to check if DFA_min for B = DFA_min (∑*).
Hence both (A) and (B) are decidable.
For every PDA we can covert it into a CFG, minimize the CFG (removing all useless symbols and productions), if Start symbol is useless then we can say 'Yes', otherwise we can say 'No'. Hence (C) is decidable.
Only option left is (D). It is undecidable, There's no way to determine if a CFG can generate everything or not.
Final ans is D.

Q3: The set of all recursively enumerable languages is  (2018)
(a) closed under complementation
(b) closed under intersection.
(c) a subset of the set of all recursive languages.
(d) an uncountable set
Ans: (b)
Sol:
C is false as the set of all recursively enumerable languages (semi-decidable) is a STRICT super set of the set of all recursive languages (decidable).
D is false as the set of all recursively enumerable languages (set of all Turing machines) is an infinite but countable set.

Q4: 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 Y reduces to W, and Z reduces to X (reduction means the standard many-one-reduction).  (2016 SET-1)
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.
Ans: (c)
Sol: 
X is recursive language, sois also recursive.
Y is recursively enumerable, but not recursive sois not recursively enumerable language.
A ≤ B, (A is reducible to B), i. e, solving A cannot be "harder" than solving B.

1. If A is reducible to B, and B is decidable, then A is decidable.
    i) if A is reducible to B, and B is recursive, then A is recursive.
2. If A is undecidable and reducible to B, then B is undecidable.
    i) if B is recursively enumerable, and A is reducible to B, then A is recursively enumerable.
    ii) if A is not recursively enumerable, and reducible to B, then B is not recursively enumerable.

Now Back to question.
is not recursively enumerable, and reducible to W, then W is not recursively enumerable (using 2(ii)).
Z is reducible toandis recursive, then Z is recursive (using 1(i)).
Option C is correct.

Q5: Let L be a language and I be its complement. Which of the following is NOT a viable possibility?  (2014 SET-1)
(a) Neither L noris recursively enumerable (r.e.).
(b) One of L andis r.e. but not recursive; the other is not r.e.
(c) Both L andare r.e. but not recursive
(d) Both L andare recursive.
Ans: (c)
Sol: 
(C) is not possible. If L is re we have a TM that accepts a string in L. Ifis re, we have a TM that accepts strings in.
So, using both these TMs we can make a new TM M which accepts strings in L and rejects strings in- that is M decides L, making L recursive.

Q6: Let L₁ be a recursive language. Let L₂ and L₃ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?  (2010)
(a) L₂ - L₁ is recursively enumerable.
(b) L₁ - L₃ is recursively enumerable.
(c) L₂ ∪ L₁ is recursively enumerable.
(d) L₂ ∩ L₁ is recursively enumerable.
Ans: (b)
Sol:

Recursive languages are closed under complement, and sois recursive and hence recursively enumerable also. So is recursively enumerable is always TRUE.

Recursively enumerable languages are not closed under complement. So,may or may not be recursively enumerable and hence we can't say anything ifis recursively enumerable or not.
C. Intersection of two recursively enumerable languages is always recursively enumerable (RE closed under intersection).
D. Union of two recursively enumerable languages is always recursively enumerable(RE closed under union).
Correct Answer: B