Let L1 be a recursive language, and let L2 be a recursively enumerable but not…
2005
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?
L1' --> Complement of L1
L2' --> Complement of L2 - A.
L1' is recursive and L2' is recursively enumerable
- B.
L1' is recursive and L2' is not recursively enumerable
- C.
L1' and L2' are recursively enumerable
- D.
L1' is recursively enumerable and L2' is recursive
Attempted by 15 students.
Show answer & explanation
Correct answer: B
L1 is recursive, so its complement L1' must also be recursive because recursive languages are closed under complement. L2 is recursively enumerable but not recursive, meaning it cannot be decided by a Turing machine. The complement of such a language (L2') is not recursively enumerable, as this would imply L2 is recursive—a contradiction. Therefore, L1' is recursive and L2' is not recursively enumerable.
A video solution is available for this question — log in and enroll to watch it.