Question:medium

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?

Show 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.
Updated On: Jul 22, 2026
  • \(L_1\) is regular
  • \(L_1 \cup L_2\) is regular
  • \(\overline{L_2}\) is context-free
  • \(L_1\) is context-free
Show Solution

The Correct Option is C

Solution and Explanation

Step 1: Restate what is actually promised. Only two regularity facts are handed to us: \(L_1 \cap L_2\) is regular, and \(L_2\) is regular. \(L_1\) itself is completely unconstrained apart from that intersection fact, so any property that would require knowing something about \(L_1\) directly cannot be forced to hold.
Step 2: Work option by option using the closure-property toolbox instead of a single combined counterexample.
Step 3: Option (C) first, since it is the one that does not need \(L_1\) at all. Closure of REG under complement: given a DFA for \(L_2\) (which exists because \(L_2\) is regular), swapping accepting and non-accepting states yields a DFA for \(\overline{L_2}\), so \(\overline{L_2}\) is regular. Since \(REG \subseteq CFL\) (every regular language is generated by some context-free grammar, e.g. by converting its DFA to an equivalent right-linear grammar), \(\overline{L_2}\) is context-free. This chain of closure facts uses nothing about \(L_1\), so it is unconditionally true. (C) holds.
Step 4: Option (A). If \(L_1\) were forced to be regular whenever \(L_1 \cap L_2\) is regular and \(L_2\) is regular, that would mean intersecting with a regular set can never "hide" irregularity, which is false in general - choosing \(L_2=\emptyset\) makes \(L_1 \cap L_2 = \emptyset\) regular regardless of how wild \(L_1\) is, e.g. \(L_1 = \{a^{n}b^{n}c^{n}: n\geq0\}\), a non-regular, non-context-free language. So (A) fails.
Step 5: Option (B). \(L_1 \cup L_2\) with \(L_2 = \emptyset\) reduces to \(L_1\) again, which is \(\{a^{n}b^{n}c^{n}\}\), not regular. So (B) fails.
Step 6: Option (D). The same \(L_1 = \{a^{n}b^{n}c^{n}\}\) fails the context-free pumping lemma (splitting any candidate string \(uvwxy\) with \(|vwx| \leq n\) and pumping \(v,x\) unbalances the counts of a's, b's, c's for large enough n), so it is not context-free. So (D) fails.
Step 7: Every option other than (C) is defeated by the same single example \(L_2=\emptyset\), \(L_1=\{a^{n}b^{n}c^{n}\}\), while (C) is proved directly from closure properties without needing any example at all.
\[ \boxed{\text{Correct option: (C) only}} \]
Was this answer helpful?
1

Questions Asked in GATE CS exam