RecursiveEnumerableLanguages
Question 1 
W can be recursively enumerable and Z is recursive.  
W can be recursive and Z is recursively enumerable.  
W is not recursively enumerable and Z is recursive.  
W is not recursively enumerable and Z is not recursive. 
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.
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?
L2 – L1 is recursively enumerable
 
L1 – L3 is recursively enumerable
 
L2 ∩ L1 is recursively enumerable
 
L2 ∪ L1 is recursively enumerable 
Question 2 Explanation:
L2 − L1 means L2 ∩ L1^{c} , since L1 is recursive hence L1^{c} must also be recursive, So L2∩L1^{c} 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 ∩ L3^{c} , since recursive enumerable is not closed under complement, so L3^{c} 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.
L1 − L3 means L1 ∩ L3^{c} , since recursive enumerable is not closed under complement, so L3^{c} 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 
regular  
contextfree  
contextsensitive  
recursive 
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.
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?
Every NFA can be converted to an equivalent DFA  
Every nondeterministic Turing machine can be converted to an equivalent deterministic Turing machine
 
Every regular language is also a contextfree language
 
Every subset of a recursively enumerable set is recursive 
Question 4 Explanation:
Every NFA can be converted into DFA (as there exist a standard procedure to convert NFA into DFA). Also, every nondeterministic 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 L_{1} be a recursive language, and let L_{2} be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
Question 5 Explanation:
Recursive languages are closed under complementation.
But, recursive enumerable languages are not closed under complementation.
If L_{1} is recursive, then L_{1}', is also recursive.
If L_{2} is recursive enumerable, then L_{2}', is not recursive enumerable language.
But, recursive enumerable languages are not closed under complementation.
If L_{1} is recursive, then L_{1}', is also recursive.
If L_{2} is recursive enumerable, then L_{2}', is not recursive enumerable language.
Question 6 
Both S_{1} and S_{2} are true
 
S_{1} is true but S_{2} is not necessarily true
 
S_{2} is true but S_{1} is not necessarily true  
Neither is necessarily true

Question 6 Explanation:
Given that
L_{1} = recursively enumerable language
L_{2} over Σ∪{#} as {w_{i}#w_{j}  w_{i}, w_{j} ∈ L_{1}, i < j}
S_{1} is True.
If L_{1} is recursive then L_{2} is also recursive. Because, to check w = w_{i}#w_{j} belongs to L_{2}, and we give w_{i} and w_{j} to the corresponding decider L_{1}, if both are to be accepted, then w∈L_{1} and not otherwise.
S_{2} is also True:
With the corresponding decider L_{2} we need to make decide L_{1}.
L_{1} = recursively enumerable language
L_{2} over Σ∪{#} as {w_{i}#w_{j}  w_{i}, w_{j} ∈ L_{1}, i < j}
S_{1} is True.
If L_{1} is recursive then L_{2} is also recursive. Because, to check w = w_{i}#w_{j} belongs to L_{2}, and we give w_{i} and w_{j} to the corresponding decider L_{1}, if both are to be accepted, then w∈L_{1} and not otherwise.
S_{2} is also True:
With the corresponding decider L_{2} we need to make decide L_{1}.
Question 7 
Nobody knows yet if P = NP. Consider the language L defined as follows :
Which of the following statements is true ?
L is recursive
 
L is recursively enumerable but not recursive  
L is not recursively enumerable
 
Whether L is recursive or not will be known after we find out if P = NP

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