Non regular context-free language and infinite regular sublanguages

Question

I had a work for the university which basically said:

"Demonstrates that the non-regular language L={0^n 1^n : n natural} had no infinite regular sublanguages."

I demonstrated this by contradiction. I basically said that there is a language S which is a sublanguage of L and it is a regular language. Since the possible Regular expressions for S are 0*, 1*, (1+0)* and (0o1)*. I check each grammar and demonstrate that none of them are part of the language L.

However, how I could prove that ANY non regular context free language could not contain any regular infinite sublanguages?

I don't want the prove per se, I just want to be pointed in the right direction.

Answer 1

For the 0^n 1^n language, it might be valuable to look into the pumping lemma. I think when I learned the pumping lemma it was used on the a^n b^n language (same thing.) Possibly the pumping lemma might help in your proof.

Also you can consider that regular languages are closed under complement, union, intersection, and the kleene star.

That is if L1 and L2 are regular then:

L1 L2 (concatenation) is also regular.
L1 n L2 is regular
L1 U L2 is regular
¬L1 is regular 
L1* is regular

It's possible that you could prove that any language that contains an regular infinite sublanguage is regular by using some of these rules.

Answer 2

EDIT: false statement, only applies to context free language

Answer 3

Since you just want hints (and thankfully so, since I forgot how to do proofs since college), look at the definition of a regular language and what properties it has. Just from looking there I had enough info to prove the statement.

Answer 4

Your instincts are good. Two things here.

First, almost always when the question takes the form "show that L is not regular/not CF" the answer is going to involve using the pumping lemmas. Similarly, when you get a question like "show there are no X that ..." the easy route is (almost always) going to be a proof by contradiction.

Answer 5

L = {0^n 1^n : n natural} is non-regular context free.

M = 2*3* is infinite regular.

N = L∪M is non-regular context free. N contains M.