Which of the following is true? A. The complement of a recursive language is recursive B. The complement of a recursively enumerable language is recursively enumerable C. The complement of a recursive language is either recursive or recursively enumerable D. The complement of a context-free language is context-free

GATE 2002 · Theory of Computation · Closure Property · easy

Answer: A. The complement of a recursive language is recursive.

1. Verify Option A: complement of recursive is recursive: Let M be a TM deciding L. Construct M': on input w, simulate M on w. If M accepts, M' rejects. If M rejects, M' accepts. Since M always halts, M' always halts. M' decides complement(L). Therefore complement of recursive language is recursive. Option A is TRUE.
2. Verify Option B: complement of RE is RE: This is FALSE. By Rice's theorem consequences and direct proof: if L is RE but not recursive, then complement(L) is NOT RE. Proof: if both L and complement(L) were RE (with TMs M1 and M2), run M1 and M2 in parallel on input w; one must halt, giving a decider for L — contradicting L not being recursive.
3. Eliminate options C and D: Option C says complement of recursive is either recursive or RE. But A already says it's always recursive (a stronger and correct statement). Option D says complement of CFL is CFL — FALSE since CFLs are not closed under complementation. The correct answer is A.