2
$\begingroup$

If $L_1$ is a regular language and $L_1 \cap L_2$ is a context-free language, does it mean that $L_2$ is a context-free language too?

I attempted to prove that $L_2$ was not required to be context-free by the following: If $L_1 = \{ a^n \}$ and $L_2 = \{ a^nb^nc^n \} $ then $L_1 \cap L_2 = \{ a^n \}$ which is context-free.

Is this a counterexample to show that $L_2$ is not required to be context-free? If not, then do you have any suggestions?

$\endgroup$
3
  • 7
    $\begingroup$ With your choices, $L_1 \cap L_2 = \{\varepsilon\}$. $\endgroup$
    – Raphael
    Mar 24, 2014 at 10:47
  • 1
    $\begingroup$ with a tiny bit of editing you have your answer. $\endgroup$
    – babou
    Mar 24, 2014 at 11:08
  • $\begingroup$ OP having solved his own problem (albeit with a small mistake), I think the question can be closed. $\endgroup$ Mar 24, 2014 at 14:52

0