GATE CS 2002 Q2.14 — Regular and Context-free Languages

Let's analyze each option based on the closure properties of language families:

1. The complement of a recursive language is recursive:
   True. Recursive languages (decidable languages) are closed under complementation. If a language $L$ is decided by a Turing Machine $M$ (which halts on all inputs), we can construct a Turing Machine $M'$ to decide the complement $\overline{L}$ by swapping the accepting and non-accepting halting states of $M$. Since $M$ always halts, $M'$ also always halts. Thus, $\overline{L}$ is recursive.
2. The complement of a recursively enumerable language is recursively enumerable:
   False. Recursively enumerable (RE) languages are not closed under complementation. If a language $L$ and its complement $\overline{L}$ are both RE, then $L$ must be recursive. Since there exist languages that are RE but not recursive (such as the Halting Problem), their complements are not RE.
3. The complement of a recursive language is either recursive or recursively enumerable:
   Since the complement of a recursive language is strictly recursive, Option A is the standard and precise statement of the closure property.
4. The complement of a context-free language is context-free:
   False. Context-free languages are not closed under complementation. For example, the languages $L_1 = \{a^n b^n c^m \mid n, m \ge 0\}$ and $L_2 = \{a^m b^n c^n \mid n, m \ge 0\}$ are context-free, but their intersection $L_1 \cap L_2 = \{a^n b^n c^n \mid n \ge 0\}$ is not context-free. Since intersection can be expressed using union and complementation ($L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$) and CFLs are closed under union, they cannot be closed under complementation.

Therefore, the correct option is A.