If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?

Problem Detail: 

Say, $L \subseteq \{0\}^*$. Then how can we prove that $L^*$ is regular?

If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular. Also I have noticed that, for $L = \{0^p \mid p \text{ is a prime}\}$, $L$ is not regular, $L \subseteq \{0\}^*$ and $L^*$ is regular.

But how to show this for any subset $L$ of $\{0\}^*$ ?

Asked By : ChesterX

Answered By : Patrick87

Assume that $L$ contains two words $w_1$ and $w_2$ such that the lengths of these words, $|w_1|$ and $|w_2|$, have no factors in common. Then, we have that the longest word that cannot be formed by concatenating these words has length $(|w_1|-1)(|w_2|-1) - 1$ (Frobenius number). That is to say, if there are words in the language whose lengths don't have a common factor, then all words of a certain minimal length are in the language $L^*$. It's easy to see this is regular since, of necessity, there are a finite number of equivalence classes under the Myhill-Nerode indistinguishability relation.

What if the lengths of all words in $L$ share a common factor? Well, It's not hard to see that in such cases, $L^*$ is also regular. Simply note that instead of all words whose lengths are greater than some minimal length being in $L^*$, it will instead be true that all words whose lengths are a multiple of the GCD of word lengths will be in $L^*$, and no words whose lengths aren't multiples of this GCD will be, and since $(L^k)^*$ is regular for any integer $k$, $L^*$ is also regular.

This is pretty informal, but everything you need to formalize this should be here.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10013