Let \(L\) be a language and \(\overline L\) be its complement. Which one of…
2014
Let \(L\) be a language and \(\overline L\) be its complement. Which one of the following is NOT a viable possibility?
- A.
Neither
\(L\)nor\(\overline L\)is recursively enumerable (r.e.). - B.
One of
\(L\)and\(\overline L\)is r.e. but not recursive; the other is not r.e. - C.
Both
\(L\)and\(\overline L\)are r.e. but not recursive. - D.
Both
\(L\)and\(\overline L\)are recursive.
Attempted by 81 students.
Show answer & explanation
Correct answer: C
Key idea: if both a language and its complement are recursively enumerable, then the language is actually recursive.
Reasoning:
Assume both the language and its complement have recognizers (semi-decision procedures).
On an input x, run both recognizers in parallel (dovetail their steps).
Exactly one recognizer will eventually accept x, depending on whether x is in the language or in its complement. When a recognizer accepts, halt and answer accordingly.
Therefore the procedure always halts with the correct membership answer, so the language is decidable (recursive).
Conclusion:
It is impossible for both the language and its complement to be r.e. yet both be non-recursive; if both were r.e. then they would be recursive.
Thus the statement that both the language and its complement are r.e. but not recursive is not a viable possibility.
A video solution is available for this question — log in and enroll to watch it.