GATE CS 2016 Set 2 Q18 — Regular and Context-free Languages

To determine which statements are true, let us analyze the closure properties of the given language classes:

• $L_1$: Regular
• $L_2$: Context-free (CFL)
• $L_3$: Recursive (Decidable)
• $L_4$: Recursively Enumerable (RE / Turing-recognizable)

Statement I: $\overline{L_3} \cup L_4$ is recursively enumerable.

• Since $L_3$ is recursive, its complement $\overline{L_3}$ is also recursive.
• Every recursive language is also recursively enumerable (RE), so $\overline{L_3}$ is RE.
• Since $L_4$ is RE and the class of RE languages is closed under union, the union $\overline{L_3} \cup L_4$ is recursively enumerable.
• Therefore, Statement I is TRUE.

Statement II: $\overline{L_2} \cup L_3$ is recursive.

• Every context-free language is recursive ($L_2 \subseteq L_3$). Thus, $L_2$ is recursive.
• Since recursive languages are closed under complementation, $\overline{L_2}$ is recursive.
• Since both $\overline{L_2}$ and $L_3$ are recursive, and recursive languages are closed under union, $\overline{L_2} \cup L_3$ is recursive.
• Therefore, Statement II is TRUE.

Statement III: $L_1^* \cap L_2$ is context-free.

• Since $L_1$ is regular, its Kleene closure $L_1^*$ is also regular.
• $L_2$ is context-free.
• The intersection of a regular language and a context-free language is always context-free ($CFL \cap Regular = CFL$).
• Therefore, Statement III is TRUE.

Statement IV: $L_1 \cup \overline{L_2}$ is context-free.

• $L_2$ is context-free, but context-free languages are not closed under complementation. Thus, $\overline{L_2}$ is not necessarily context-free.
• If we choose $L_1 = \emptyset$ (which is regular), then $L_1 \cup \overline{L_2} = \overline{L_2}$, which may not be context-free.
• Therefore, Statement IV is FALSE.

Since statements I, II, and III are true, the correct option is D.