-
Let L be a language and L be its complement. Which one of the following is NOT a viable possibility?
-
- Neither L nor L is recursively enumerable (r.e.).
- One of L and L is r.e. but not recursive; the other is not r.e.
- Both L and L are r.e. but not recursive.
- Both L and L are recursive.
- Neither L nor L is recursively enumerable (r.e.).
Correct Option: C
Both L and L are recursively enumerable but not recursive.
Set of recursive languages is subset of the set of recursively enumerable languages.
So, if a language is recursive, It must be R.E. also.
(a) May be true as a language L and its complement L need not be recursively enumerable.
(b) May be true if L is r.e. but not recursive and L is not recursively enumerable
(d) May be true as L and L both can be recursive.
However (c) is not possible because if Both L and L are recursively enumerable than by a well known theorem of complexity theory either L or L has to be recursive.
