Which of the following is true?

GATE · 2002 · CS · Question 2 subparts· Modified — slightly modified from the official paper; see the solution

1. A.

   The complement of a recursive language is recursive.

2. B.

   The complement of a recursively enumerable language is recursively enumerable.

3. C.

   The complement of a recursive language is neither recursive nor recursively enumerable.

4. D.

   The complement of a context-free language is context-free.

Attempted by 154 students.