Recursive-and-Recursively-Enumerable-Language
Question 1 |
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 |
P = NP (or) P != NP
→ If P=NP then L=(0+1)* which is regular, then it is recursive.
→ If P!=NP then L becomes ɸ which is also regular, then it is recursive.
So, finally L is recursive.
Question 2 |
L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, ... Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i < j}. Here # is a new symbol. Consider the following assertions.
S1: L1 is recursive implies L2 is recursive S2: L2 is recursive implies L1 is recursive
Which of the following statements is true?
Both S1 and S2 are true
| |
S1 is true but S2 is not necessarily true | |
S2 is true but S1 is not necessarily true | |
Neither is necessarily true
|
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 3 |
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?
 | |
 | |
 | |
 |
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 4 |
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 
reduces to W, and Z reduces to 
(reduction means the standard many-one reduction). Which one of the following statements is TRUE?
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. |
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.