Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The question is as follows:

 If L1 and L2 are not regular and L1 ⊆ L ⊆ L2, then L is regular

My intuition says that it's wrong so I've been looking for a counterexample, so far I didn't succeed.

Can I please get a direction? is this claim might be true?

Thanks in advance

share|cite|improve this question
What about $L_1 = L_2$? – Hendrik Jan Dec 7 '12 at 12:57
I don't think I may do that. Besides, even if L1=L2, I can find a language L that is contained in it and regular, so it doesn't disproves the claim. – DanielY Dec 7 '12 at 12:59
If $L_1=L_2$ is not regular, then $L=L_1$ saisfies all conditions, and cannot be regular. If that is not what you need or want, please rephrase the question. You might want to add "for all" or "there exist". – Hendrik Jan Dec 7 '12 at 13:02
No, that's probably the counterexample I was looking for, thanks alot :) Can you leave an answer so I can accept it? – DanielY Dec 7 '12 at 13:15
up vote 2 down vote accepted

If you take $L_1=L_2$ not regular, then $L=L_1$ satisfies your assumptions, but cannot be regular.

share|cite|improve this answer

Your Answer


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.