GATE CS 2015 Set 1 Q3 — Turing Machines

We analyze each statement based on the closure properties of language families:

• Statement I: Every context-free language is also a recursive language. Since recursive languages are closed under complementation, if $L_1$ is context-free, then $\bar{L}_1$ must be recursive. This statement is true.
• Statement II: If $\bar{L}_2$ were recursive, then its complement $L_2$ would also be recursive. Since we are given that $L_2$ is not recursive, $\bar{L}_2$ cannot be recursive. This statement is false.
• Statement III: Context-free languages are not closed under complementation. Thus, $\bar{L}_1$ is not necessarily context-free. This statement is false.
• Statement IV: Since $L_1$ is context-free, $\bar{L}_1$ is recursive, which implies $\bar{L}_1$ is recursively enumerable (RE). Since $L_2$ is RE and RE languages are closed under union, $\bar{L}_1 \cup L_2$ must be recursively enumerable. This statement is true.

Hence, only statements I and IV are necessarily true.