NIELIT 2017 July Scientist B (CS) - Section B: 60

Question

Let $L1$ be a recursive language, and let $L2$ be a recursively enumerable but not recursive language. Which one of the following is TRUE?

• A. $L1’$ is recursive and $L2’$is recursively enumerable.
• B. $L1’$ is recursive and $L2’$is not recursively enumerable.
• C. $L1’$ and $L2’$is recursively enumerable.
• D. $L1’$ is recursively enumerable and $L2’$is recursive.

Comments

option b

recursive is closed in complement

recursive enumerable is not closed in complement

Answer 1

Option B

Comments

explanation??

---

Recursive languages are closed under complementation.
But, recursive enumerable languages are not closed under complementation.

Answer 2

Recursive languages are closed under complementation.
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.

Answer 3

Here it is given that L1 is recursive so by the closure property of recursive language we can say that L1' is also recursive.
but the same doesn't work for RE, A complement of RE which is not recursive isn' RE so option B is correct.

Reference: https://courses.engr.illinois.edu/cs373/sp2013/Lectures/lec26.pdf