## Recursive-Enumerable-Languages

 Question 1
 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.
Theory-of-Computation       Recursive-Enumerable-Languages       2016 set-01
Question 1 Explanation:
The rules are:
If A ≤ p B
Rule 1: If B is recursive then A is recursive
Rule 2: If B is recursively enumerable then A is recursively enumerable
Rule 3: If A is not recursively enumerable then B is not recursively enumerable
Since X is recursive and recursive language is closed under compliment, so is also recursive.
: By rule 3, W is not recursively enumerable.
: By rule 1, Z is recursive.
Hence, W is not recursively enumerable and Z is recursive.
 Question 2
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 ∩ L1 is recursively enumerable D L2 ∪ L1 is recursively enumerable
Theory-of-Computation       Recursive-Enumerable-Languages       2010
Question 2 Explanation:
L2 − L1 means L2 ∩ L1c , since L1 is recursive hence L1c must also be recursive, So L2∩L1c is equivalent to (Recursive enum ∩ Recursive) , as every recursive is recursive enum also, so it is equivalent to (Recursive enum ∩ Recursive enum) and recursive enum is closed under intersection, so L2− L1 must be recursive enumerable. Hence A is always true.
L1 − L3 means L1 ∩ L3c , since recursive enumerable is not closed under complement, so L3c may or may not be recursive enumerable, hence we cannot say that L1 − L3 will always be recursive enumerable. So B is not necessarily true always.
L2 ∩ L1 means (Recursive enum ∩ Recursive) , as every recursive is recursive enum also, so it is equivalent to (Recursive enum ∩ Recursive enum) and recursive enum is closed under intersection, so L2∩ L1 must be recursive enumerable. Hence C is always true.
L2 ∪ L1 means (Recursive enum ∪ Recursive) , as every recursive is recursive enum also, so it is equivalent to (Recursive enum ∪ Recursive enum) and recursive enum is closed under union, so L2 ∪ L1 must be recursive enumerable. Hence D is always true.
 Question 3
 A regular B context-free C context-sensitive D recursive
Theory-of-Computation       Recursive-Enumerable-Languages       Gate-2008
Question 3 Explanation:
If L is recursive enumerable, then it implies that there exist a Turing Machine (lets say M1) which always HALT for the strings which is in L.
If are recursively enumerable, then it implies that there exist a Turing Machine (lets say M2) which always HALT for the strings which is NOT in L(as L is complement of Since we can combine both Turing machines (M1 and M2) and obtain a new Turing Machine (say M3) which always HALT for the strings if it is in L and also if it is not in L. This implies that L must be recursive.
 Question 4
Which of the following statements is false?
 A Every NFA can be converted to an equivalent DFA B Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine C Every regular language is also a context-free language D Every subset of a recursively enumerable set is recursive
Theory-of-Computation       Recursive-Enumerable-Languages       Gate-2008
Question 4 Explanation:
Every NFA can be converted into DFA (as there exist a standard procedure to convert NFA into DFA). Also, every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine. Every regular language is also a CFL , since if a language can be recognized by Finite automata, then it must also be recognize by PDA (as PDA is more powerful than FA). But every subset of recursively enumerable need not be recursive.
 Question 5
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
 A B C D Theory-of-Computation       Recursive-Enumerable-Languages       Gate-2005
Question 5 Explanation:
Recursive languages are closed under complementation.
But, recursive enumerable languages are not closed under complementation.
If L1 is recursive, then L1', is also recursive.
If L2 is recursive enumerable, then L2', is not recursive enumerable language.
 Question 6
 A Both S1 and S2 are true B S1 is true but S2 is not necessarily true C S2 is true but S1 is not necessarily true D Neither is necessarily true
Theory-of-Computation       Recursive-Enumerable-Languages       Gate-2004
Question 6 Explanation:
Given that
L1 = recursively enumerable language
L2 over Σ∪{#} as {wi#wj | wi, wj ∈ L1, i < j}
S1 is True.
If L1 is recursive then L2 is also recursive. Because, to check w = wi#wj belongs to L2, and we give wi and wj to the corresponding decider L1, if both are to be accepted, then w∈L1 and not otherwise.
S2 is also True:
With the corresponding decider L2 we need to make decide L1.
 Question 7
Nobody knows yet if P = NP. Consider the language L defined as follows : Which of the following statements is true ?
 A L is recursive B L is recursively enumerable but not recursive C L is not recursively enumerable D Whether L is recursive or not will be known after we find out if P = NP
Theory-of-Computation       Recursive-Enumerable-Languages       Gate-2003
Question 7 Explanation:
Here, we have two possibilities, whether
P = NP (or) P != NP
→ If P=NP then L=(0+1)* which is recular, then it is recursive.
→ If P!=NP then L becomes ɸ which is also regular, then it is recursive.
So, finally L is recursive.
There are 7 questions to complete.