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