Question

Let 𝐿1 and 𝐿2 be two languages over a finite alphabet, such that 𝐿1 ∩𝐿2 and 𝐿2 are
regular languages.
Which of the following statements is/are always true?

• A. 𝐿1 is regular
• B. 𝐿1 ∪𝐿2 is regular
• C. 𝐿2 is context-free
• D. 𝐿1 is context-free

Hint:

Recall the Chomsky hierarchy: every regular language is automatically context-free. Since \(L_2\) is given to be regular, it must be context-free regardless of \(L_1\). Try a counterexample like \(L_1 = \{a^n b^n c^n\}\) with \(L_2\) finite to see why the other three options can fail.

Answer 1

The Correct Option is C

This question tests the closure and containment relationships among regular, context-free, and arbitrary languages, given that \(L_1 \cap L_2\) and \(L_2\) are regular.

Step 1: The Chomsky hierarchy states Regular \(\subseteq\) Context-Free \(\subseteq\) Context-Sensitive \(\subseteq\) Recursively Enumerable. Any language that is regular is automatically context-free too, independent of any other language it is combined with.

Step 2: Since the problem states \(L_2\) is regular, by the hierarchy fact above, \(L_2\) must be context-free. This makes option (c) unconditionally true, no matter what \(L_1\) turns out to be.

Step 3: Now test whether \(L_1\) is forced to be regular or context-free. Consider \(L_1 = \{a^n b^n c^n : n \geq 1\}\), a well-known language that is not context-free because it requires three counts to match simultaneously, which no pushdown automaton can verify. Choose \(L_2 = \{abc\}\), a finite and therefore regular language. Then \(L_1 \cap L_2 = \{abc\}\) (the single string with n=1), which is finite and hence regular. Both given hypotheses hold: \(L_1 \cap L_2\) is regular and \(L_2\) is regular.

Step 4: In this scenario \(L_1\) itself is neither regular nor context-free, so options (a) and (d) collapse. Also \(L_1 \cup L_2 = L_1\) (since abc is already in \(L_1\)), which is likewise not regular, so option (b) collapses too.

Step 5: Only the claim about \(L_2\) survives every attempted counterexample, precisely because it depends solely on the given fact that \(L_2\) is regular and not on any property of \(L_1\).

Final answer: option (C), \(L_2\) is context-free.