If language L is not regular, is L* regular?

Question

It makes sense to assume that L* is not regular. However, I cannot find a proof of either conclusion.

Answer 1

Not necessarily, but possibly. Say L is 0, 1, 01, 0011, 000111, 00001111, etc. L is not regular, but L* is just [01]*.

Answer 2

Suppose L is any language over the alphabet Σ. If L is not regular then so is L+Σ, yet (L+Σ)∗=Σ∗ is regular. So you can see that L* is not always not regular.

Answer 3

Assume L={a^n , n=k! , k>=1}. As you know this language is not regular. But L*={a^m, m>=0} or L*(r)=a* ,L* is a regular language. So this proposition is not always true.

Answer 4

If L is nonregular, L* can be either regular or nonregular, depending upon the language L.

Let L be the language {a^p | p is a prime number}. L* contains all strings of length two and above since it contains all linear combinations of strings aa and aaa. L* is regular since it is the set difference of the regular languages a* and {a}, and the regular languages are closed under set difference.

Let L = {a^n b^n | n > 0}. A string in L* of length at least p (where p is the pumping length of the pumping lemma) is a^p b^p. Pumping canchange only the number of a's and cannot give us another string in the language, so L* is not regular.

Note an interesting fact: L* is always regular if L is a language over an alphabet with just one symbol in it. The first example I gave illustrates why this must always be the case.