CODEWITHSUNDEEP
regexnlpcontext-free-grammar
Freddy
Freddy

Reputation: 3274

Non regular context-free language and infinite regular sublanguages

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.

Upvotes: 4

Views: 4380

Answers (5)

Windows programmer
Windows programmer

Reputation: 8065

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.

Upvotes: 3

Charlie Martin
Charlie Martin

Reputation: 112366

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.

Upvotes: 2

MSN
MSN

Reputation: 54584

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.

Upvotes: 0

eulerfx
eulerfx

Reputation: 37719

EDIT: false statement, only applies to context free language

Upvotes: 0

Perchik
Perchik

Reputation: 5620

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.

Upvotes: 3

Related Questions