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.

Fundus

A subset of a regular language is not necessarily regular: 0^n1^n is a subset of 0*1*, after all. – Anselmo

Thanks for the reply, I was having trouble thinking of an example. – Fundus

This is a little off-topic; you'll probably get a better response at cs.stackexchange.com. – Anselmo

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!

Dempster

Did you mean Whole Numbers and not Natural Numbers? (for the language L) – Bugaboo

@Tinkidinki I did intend to use natural numbers there. I haven’t seen the term whole numbers used in formal mathematics before, though I definitely remember learning about them in primary school. – Dempster

Answer 2

Take L = {a,b}*, which is regular, but has a non-regular subset L={a^n b^n} (this one can be proved to be non regular by pumping lemma...), so it's not the case that all subsets of a regular language are regular.

Istle

I'm pretty sure that answers your questions after two years :D – Istle

Yeah my bad a^n b^n – Istle

My apologies - I see what you were going for here. If you edit your answer to address the fact that you're pointing out that the claim "If L is regular, then every subset of L is regular" is false, I'll replace the downvote with an upvote. – Dempster

You can read in parenthesis that I am saying this one can be proved to be non regular meaning if L* is regular it doesnt mean L its subset has to be also regular that's the point... – Istle

But in this case your language L = {a^n b^n | n in N } doesn't have have the property that L* = {a, b}*, since L* doesn't contain aab, for example. – Dempster

bro if a and b are both raised to the power of n that means their are equal number of a's and b's – Istle

Yes, exactly. So perhaps I misinterpreted your answer? Weren't you claiming that {a^n b^n | n in N}* = {a,b}*? – Dempster

I can't remove my downvote until you edit your answer (the site won't let me). Can you rewrite your answer to more clearly articulate your point? If so, I'll remove the downvote. – Dempster

forget it I forgot half of what I learned I didn't even like this course lol but yeah that answer is 100 percent correct i am sure – Istle