Question 13

Given:

• $L_1$ is a Context-Free Language (CFL).
• $L_2$ is Recursively Enumerable (RE) but not Recursive (REC).

Evaluating each statement:

1. Statement I ($\overline{L_1}$ is recursive): Every context-free language is recursive (decidable). The class of recursive languages is closed under complementation. Thus, $\overline{L_1}$ is always recursive. (Necessarily true)
2. Statement II ($\overline{L_2}$ is recursive): If $\overline{L_2}$ were recursive, then its complement $L_2$ would also be recursive. But $L_2$ is given to be non-recursive. Thus, $\overline{L_2}$ is not even RE, let alone recursive. (False)
3. Statement III ($\overline{L_1}$ is context-free): The class of context-free languages is not closed under complementation. For example, $L = \{a^n b^n c^n\}^c$ is a CFL whose complement is not a CFL. (Not necessarily true)
4. Statement IV ($\overline{L_1} \cup L_2$ is recursively enumerable): Since $\overline{L_1}$ is recursive, it is also RE. The union of two recursively enumerable languages ($\overline{L_1}$ and $L_2$) is always recursively enumerable because the class of RE languages is closed under union. (Necessarily true)

Therefore, Statements I and IV are necessarily true (option D).