If L and L' are recursively enumerable then L is, ISRO 2016
2016
If L and L' are recursively enumerable then L is,
ISRO 2016
- A.
Regular
- B.
Context free
- C.
Context Sensitive
- D.
Recursive
Attempted by 34 students.
Show answer & explanation
Correct answer: D
If a language L and its complement L' are both recursively enumerable, then L is recursive. This is because we can construct a Turing machine that runs the recognizers for both L and L' in parallel. For any input string, one of them must eventually halt and accept, allowing us to decide membership definitively.