Language Properties Analysis

Given: Two languages $L_1$ and $L_2$ over a finite alphabet.

• $L_2$ is regular.
• $L_1 \cap L_2$ is regular.

We must determine which statement is always true.

Option 3: $\overline{L_2}$ is context-free

Analysis:

• Fact 1: If a language is regular, its complement is also regular (closure property). Since $L_2$ is regular, $\overline{L_2}$ is regular.
• Fact 2: All regular languages are context-free languages.
• Conclusion: Since $\overline{L_2}$ is regular (from Fact 1), it must be context-free (from Fact 2). This statement is always true.

Options 1, 2, and 4 Are Not Always True

Option 1: $L_1$ is regular

Counterexample: Let $L_1 = \{a^n b^n \mid n \ge 0\}$ (Context-Free, not Regular) and $L_2 = \{a^k \mid k \ge 0\}$ (Regular). Then $L_1 \cap L_2 = \emptyset$ (Regular). Here, $L_1$ is not regular, violating the statement.

Option 2: $L_1 \cup L_2$ is regular

Counterexample: Using the same $L_1$ and $L_2$ as above. $L_1 \cup L_2 = \{a^n b^n \mid n \ge 0\} \cup \{a^k \mid k \ge 0\}$. This language is context-free but not necessarily regular.

Option 4: $L_1$ is context-free

Counterexample: Let $L_1$ be a language known to be recursively enumerable but not context-free (e.g., the Halting Problem encoded). Let $L_2 = \emptyset$ (Regular). Then $L_1 \cap L_2 = \emptyset$ (Regular). Here, $L_1$ is not context-free, violating the statement.

Result: Only Option 3 is always true.