Let \(L\) be a language and \(\overline L\) be its complement. Which one of…

GATE · 2014 · CS · Set 1 · Computer Science & IT

1. A.

   Neither $L$ nor $\overline L$ is recursively enumerable (r.e.).

2. B.

   One of $L$ and $\overline L$ is r.e. but not recursive; the other is not r.e.

3. C.

   Both $L$ and $\overline L$ are r.e. but not recursive.

4. D.

   Both $L$ and $\overline L$ are recursive.

Attempted by 117 students.