Question

Let \(L_1\) and \(L_2\) be two languages over a finite alphabet, such that \(L_1 \cap L_2\) and \(L_2\) are regular languages.
Which of the following statements is/are always true?

• A. \(L_1\) is regular
• B. \(L_1 \cup L_2\) is regular
• C. \(\overline{L_2}\) is context-free
• D. \(L_1\) is context-free

Hint:

Only L2's regularity is usable unconditionally (giving complement of L2 is regular, hence context-free); try L2 = empty set to see that nothing about L1 is forced.

Answer 1

The Correct Option is C

Step 1: Concept.
The regular languages are closed under complement (if \(L\) is regular then \(\overline{L}\) is regular), and every regular language is also a context-free language (the regular languages form a strict subset of the context-free languages). We are given only that \(L_1 \cap L_2\) is regular and that \(L_2\) is regular; nothing at all is assumed about \(L_1\) beyond that.

Step 2: Build a single counterexample family that will kill several options at once.
Pick \(L_2 = \emptyset\) (the empty language, which is regular), and pick \(L_1 = \{a^{n}b^{n}c^{n} : n \geq 0\}\), a language that is known to be neither regular nor context-free (it fails the context-free pumping lemma). Then \(L_1 \cap L_2 = \emptyset\), which is regular, so this pair satisfies the given premise exactly.

Step 3: Test option (A), "\(L_1\) is regular".
In the counterexample of Step 2, \(L_1 = \{a^{n}b^{n}c^{n}\}\) is not regular. So (A) is FALSE in general.

Step 4: Test option (B), "\(L_1 \cup L_2\) is regular".
With \(L_2=\emptyset\), \(L_1 \cup L_2 = L_1 = \{a^{n}b^{n}c^{n}\}\), which is not regular. So (B) is FALSE in general.

Step 5: Test option (D), "\(L_1\) is context-free".
The same \(L_1 = \{a^{n}b^{n}c^{n}\}\) is not context-free either (this is the textbook example used to show context-free languages are not closed under intersection with regular languages, but on its own it is simply not context-free). So (D) is FALSE in general.

Step 6: Test option (C), "\(\overline{L_2}\) is context-free".
We are directly given that \(L_2\) is regular. Regular languages are closed under complementation, so \(\overline{L_2}\) is regular. Every regular language is context-free (the containment REG \(\subseteq\) CFL always holds), so \(\overline{L_2}\) is context-free. This uses only the given fact that \(L_2\) is regular and holds no matter what \(L_1\) is, so (C) is ALWAYS true.

Step 7: Conclusion.
Only option (C) is guaranteed by the premise; (A), (B), (D) all fail for the explicit choice \(L_2=\emptyset,\ L_1=\{a^{n}b^{n}c^{n}\}\).

\[ \boxed{\text{Correct option: (C) only}} \]