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.

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|improve this question
1  
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
2  
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
add comment

1 Answer

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|improve this answer
add comment

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.