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

  • $\begingroup$ 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". $\endgroup$ – 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.

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

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

However, think about this questions:

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?

By the way, explain where you are stuck and your attempt to solve this problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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