For $L_1,L_2,L_3$ , $L_1 \cap L_2 = L_3$, if $L_1,L_2,L_3$ such that $L_1 \cap L_2 = L_3$, if $L_1$ and $L_3$ are CFLs, so $L_2$ is CFGLas well

Question

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?

Everywhere in your question when you wrote «grammar» you meant «language». — Mariano Suárez-Álvarez, Aug 07 '12 at 20:45

score 3 · Accepted Answer · answered Aug 07 '12 at 20:44

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.

answered Aug 07 '12 at 20:44

Mariano Suárez-Álvarez

135,076

For a silly example, let $L_1={a^n:n\geq0}$ and $L_2=L_1\cup{b^nc^nd^n:n\geq0}$. – Mariano Suárez-Álvarez Aug 07 '12 at 20:54
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. – Mariano Suárez-Álvarez Aug 07 '12 at 20:56

For $L_1,L_2,L_3$ , $L_1 \cap L_2 = L_3$, if $L_1,L_2,L_3$ such that $L_1 \cap L_2 = L_3$, if $L_1$ and $L_3$ are CFLs, so $L_2$ is CFGLas well

1 Answers1