Toc Recursive and Recursive enumberable Language

Question

Comments

if you guys don't know the answer then atleast don't insult the question ...my friend went for iisc interview and they asked this question but she would not able to get the answer  that's why I asked you .....

---

okay, then explain what is meant by "logically follow"?

Also which CSA interview was this?- can you upload the full question paper in this question?

Answer 1

Answer : Neither L nor L' is Recursive Enumerable .

A .From theorem 1 if we consider L is a recursive Language then L' will be recursive and moreover Recursive Language's are closed under complementation..
B .As they said in option One of L and L' is Recursive .If we consider L is Recursive then from theorem 1 we can say L' is going to be Recursive and Hence Recursive Enumerable.
C .I think this does not Logically implies because from theorem 1 if we consider L is Recursive then L' will be Recursive and hence Recursive Enumerable .A/c to theorem 2 itself says if a Language and its complement L' are both Recursive Enumerable which is Contradiction of Option C.
D .If we consider L as Recursive Enumerable but not Recursive then if we take complement of L which is Recursive Enumerable we may get a Recursive Enumerable Language or not because they are not closed under Complementation. So this point is also Logically implies.

Please Let me know does this explanation make sense or is there anything wrong.

Comments

if we argue it will only become messy. Let me put it this way, based on the given theorems (which are also generally TRUE), all the 4 options can be satisfied but none are valid. i.e., based on the type of $L$ we choose, all the 4 options can be both TRUE as well as FALSE. Now, a slight modification to "B" choice

One of $L$ and $\bar{L}$ is recursive; the other is recursively enumerable but not recursive. 

Now, this statement is definitely FALSE. This is a contradiction to the given two theorems. 

---

yes yes...u r very right sir i missed it....///// sorry sir...plz don't take it as arguement...we are here to learn...and you  r here to teach us...ur little guidance can help us...

---

"Argument" is not a negative word. Good students must argue :) - it is like asking doubt. If one is asking no doubt it means either he got everything or he got nothing :)

And on a platform like this only via argument we can convey ideas. Here I told not to argue as there is a lot of ambiguity.