2

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

Bobazonski
  • 1,515
  • 5
  • 26
  • 43

4 Answers4

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.

daniel
  • 21
  • 4
  • I am not sure the "So ..." follows from what is stated beforehand... I think what you've shown is it is sometimes regular. – Patrick87 May 21 '22 at 10:56
0

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.

BarzanHayati
  • 637
  • 2
  • 9
  • 22
0

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.

Patrick87
  • 27,682
  • 3
  • 38
  • 73
-2

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