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$

closed as unclear what you're asking by Yuval Filmus, FrankW, David Richerby, vonbrand, Juho Mar 25 '14 at 18:31

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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