'If language L is not regular, is L* regular?
It makes sense to assume that L* is not regular. However, I cannot find a proof of either conclusion.
Solution 1:[1]
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.
Solution 2:[2]
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.
Solution 3:[3]
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.
Solution 4:[4]
Not necessarily, but possibly. Say L is 0, 1, 01, 0011, 000111, 00001111, etc. L is not regular, but L* is just [01]*.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | daniel |
| Solution 2 | |
| Solution 3 | Patrick87 |
| Solution 4 |