If L* is regular, then is L regular?

Question

I've tried to look for the answer and I'm getting conflicting answers so I'm not sure. I know the reverse is true, that if L is regular then L* is regular under closure.

I imagine that if L* is regular then L is regular because the subset of L* should be regular and L is part of that subset.

Answer 1

If L* is regular, then L is not necessarily regular. For example, consider any nonregular language L over an alphabet Σ such that Σ ⊆ L. (That is, imagine you have a nonregular language where each individual character in the alphabet is a string in L.) In that case, L* = Σ*, since you can form any string as the concatenation of all the individual characters of Σ.

Here's one possible example. Let Σ = {a} and consider the language L = { a²ⁿ | n ∈ N }. This language is not regular, and you can prove it using either the pumping lemma for regular languages or the Myhill-Nerode theorem. However, the language L* is the language a*, which is regular. To see this, notice that since L contains the string a, the language L* contains all strings of the form aⁿ for any natural number n.

Another option: pick L to be any nonregular language over Σ, then consider the language L ∪ Σ. This is also a nonregular language (if L ∪ Σ were regular, then we could subtract out each character added in via the union, leaving a regular language at each step, to show that L is regular), and it satisfies the above requirements.

Hope this helps!