Clever Geek Handbook

If L * is regular, then is L regular?

I've been trying to find an answer and I'm getting conflicting answers so I'm not sure. I know the converse is true, that if L is regular then L * is regular when closed.

I believe that if L * is regular, then L is regular, because the subset of L * must be regular and L is part of that subset.

+3


source to share


2 answers


If L * is regular, then L is not necessarily regular.

Here's one possible example. Let & Sigma; = {a} and consider the language L = {a 2 n | n & in; N}. This language is not regular, and you can prove it by using either the Swapping Lemma for regular languages ​​or the Mihill-Nerod Theorem. However, L * is a *, which is regular. To see this, note that since L contains a string a, L * contains all strings of the form a n for any natural n.



Hope this helps!

+3


source


Take L = {a, b} *, which is regular, but has an irregular subset L = {a ^ nb ^ n} (this can be proved not regular by the pumping lemma ...), so it is not the case that all subsets regular language are regular.



+2


source






More articles:


All Articles