Multiple choice

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?

  1. $\bar L_1$ is recursive and $\bar L_2$ is recursively enumerable
  2. $\bar L_1$ is recursive and $\bar L_2$ is not recursively enumerable
  3. $\bar L_1$ and L2 are recursively enumerable
  4. $\bar L_1$ is recursively enumerable and $\bar L_2$ is recursive
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

The rules here used will be. All those languages which are recursive their complements are also recursive. So option (1) & (2) can be correct. Now languages which are recursively enumerable but not recursive, their complements can't be recursively enumerable. So only option (2) is correct

Keep practicing — related questions