If L and L' are recursively enumerable, then L is
2008
If L and L' are recursively enumerable, then L is
- A.
regular
- B.
context-free
- C.
context-sensitive
- D.
recursive
Attempted by 20 students.
Show answer & explanation
Correct answer: D
If both L and its complement L' are recursively enumerable, then L is recursive. This follows from the fact that a language is recursive if and only if both it and its complement are recursively enumerable.
A video solution is available for this question — log in and enroll to watch it.