-1
$\begingroup$

I'm trying to answer this question:

Is it true that for three languages $L_1,L_2,L_3$ such that $L_1 \cap L_2 = L_3$, if $L_1$ and $L_3$ are context free languages, so $L_2$ is context free languages as well.

I know that context free languages are not closed under intersection, but it doesn't mean that there isn't an example for such language. I didn't come with any good idea for languages that fit the question,

Any idea?

  • 2
    Everywhere in your question when you wrote «grammar» you meant «language».2012-08-07

1 Answers 1

3

Since there exist context free languages $L_1$ which are contained in non-context free languages $L_2\supseteq L_1$, the answer is no.

  • 1
    In a different direction, it is easy to give examples of context free languages $L_1$ and non-context free languages $L_2$ which are *disjoint*, so that $L_1\cap L_2$, being empty, is context free.2019-04-13