# if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?

• Start with a warming-up statement: "if $L_1$ and $L_2$ are languages over the same alphabet and $L_1\cap L_2$ is finite, at least one of them must be finite". – Hendrik Jan Dec 15 '18 at 21:36

One way to deal with this kind of problems is to check some easy and extreme cases. Also, you would like to have a few concrete instances of the concepts involved. You should try to construct simple counterexamples with the instances. If you have found just one counterexample, great, you have found the answer. If you cannot found counterexamples by various constructions, you might have gained some understanding why it might be correct. You may have to repeat a few times.

What are some instances of non-context-free languages? Here is one. $$\{0^{n^2}\mid n\ge1\}$$. Or another one $$\{1^{n^2}\mid n\ge 1\}$$. Or another one $$\{0^{n^2+1}\mid n\ge1\}$$. How about their intersections?

In general, a condition that stipulates the type of the intersection of two languages is a very weak restriction to each of the languages. There are a lot of room for each of them to vary without changing their intersection.

Interested readers can enjoy the following simple exercises. $$L_1$$ and $$L_2$$ are are assumed to be over the same alphabet for all exercises.

Exercise 1. If $$L_1 \cap L_2$$ is finite, must at least one of them be finite?

Exercise 2. If $$L_1 \cap L_2$$ is regular, must at least one of them be regular?

Exercise 3. If $$L_1 \cap L_2$$ is context sensitive, must at least one of them be context sensitive?

Exercise 4. If $$L_1 \cap L_2$$ is decidable, must at least one of them be decidable?

Exercise 5. Raise a similar question.

• 1. Yes 2. Yes 3. (Didn't learn about context-sensitive) 4. No – sharprabbitz Dec 16 '18 at 4:04
• I am afraid you made some mistakes. – John L. Dec 16 '18 at 5:12
• 1. No 2. No 4. No – sharprabbitz Dec 16 '18 at 22:08

This is not an answer, I can't comment.

If $$L_1$$ and $$L_2$$ are context free then $$L_1∩L_2$$ is context free? And what if $$L_2$$ is a regular language?