Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Everywhere in your question when you wrote «grammar» you meant «language». –  Mariano Suárez-Alvarez Aug 7 '12 at 20:45

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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-Alvarez Aug 7 '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-Alvarez Aug 7 '12 at 20:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.