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
