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

We are given that \(L_1 \cap L_2\) and \(L_2\) are regular languages, and we need to determine which statement must always hold.

Step 1: Check option (a), 'L1 is regular'. Take \(L_2 = \{\varepsilon\}\) (regular) and \(L_1 = \{\varepsilon\} \cup \{a^n b^n c^n : n \geq 1\}\). Then \(L_1 \cap L_2 = \{\varepsilon\}\), which is regular, so both given conditions hold. But \(L_1\) itself is not regular, since it is not even context-free (by the pumping lemma for context-free languages, a language requiring three simultaneously equal counts cannot be accepted by any pushdown automaton). Hence option (a) fails.

Step 2: Check option (b), 'L1 union L2 is regular'. In the same example, \(L_1 \cup L_2 = L_1\) (since \(\varepsilon\) already belongs to \(L_1\)), which we just showed is not even context-free, so it cannot be regular either. Option (b) fails.

Step 3: Check option (d), 'L1 is context-free'. Using the same counterexample, \(L_1 = \{\varepsilon\} \cup \{a^n b^n c^n : n \geq 1\}\) is not context-free, so option (d) fails as well.

Step 4: Check option (c), 'L2 is context-free'. We are directly told that \(L_2\) is regular. By the Chomsky hierarchy, every regular language is also a context-free language, since a DFA recognizing \(L_2\) can always be treated as a pushdown automaton that never touches its stack. So \(L_2\) being regular guarantees \(L_2\) is context-free, regardless of what \(L_1\) is. This statement is always true, no counterexample can break it.

\[ \text{Regular} \subset \text{Context-Free} \quad \Longrightarrow \quad L_2 \text{ regular} \Longrightarrow L_2 \text{ context-free} \]

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