[Solved]: Kleene star of an infinite unary language always yields a regular language

Problem Detail: 

Let $L = \{a^n \mid n \ge 0\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$.

Thus $L$ consists of sequences of $a$ of all lengths, including a sequence of length $0$. Let $L_2$ be any infinite subset of $L$. I need to show there always exists a DFA to recognize $L_2^*$.

If $L_2$ is a finite subset it is very obvious as $L_2$ would be a DFA and hence by Kleene closure $L_2^*$ would be recognized by a DFA. But I am unable to get it for infinite subset as $L_2$ may not be expressed as DFA when, e.g., string lengths are prime.

Asked By : Aditya Nambiar

Answered By : Patrick87

Suppose there are two words in the language whose lengths are relatively prime. Let these lengths be $x$ and $y$. We know (see this) that by adding these numbers to each other repeatedly, we can get any number greater than $(x - 1)(y - 1) - 1$. So if $x$ and $y$ are $13$ and $7$, we can write any number greater than $72$ as a linear combination of $7$ and $13$. What this means for us: $L_2^*$ consists of some arbitrary finite language (regular, as all finite languages), in union with the language $\{w \in a^* \mid |a| > (x-1)(y-1)-1\}$. This language is regular since it is the language of all words with a finite set of words removed. Since $L_2^*$ is a union of regular languages, it must also be regular.

If all words in $L_2^*$ have lengths which share a greatest common factor (call this common factor $m$), then repeat the above argument, but instead of using string lengths, use string lengths divided by $m$. In this case, $L_2^*$ will be the concatenation of an arbitrary finite language (regular) and the language $\{w \in (a^m)^* \mid |w| > m^2[(x/m - 1)(y/m - 1) - 1]\}$, also regular (since $(a^m)^* is regular and we are removing finitely many words from it).

For example, suppose all words in $L$ have a GCF of 2, and the language contains the words $a^4$ and $a^{10}$. We have $m = 2$, $x/m = 4/2 = 2$, and $y/m = 10/2 = 5$, which are relatively prime. Therefore, we know that we can get any word whose length is multiple of $m$ if the length is greater than $m^2[(x/m - 1)(y/m - 1) - 1] = 2^2[(2 - 1)(5 - 1) - 1] = (4)(3) = 12$ by concatenating $a^4$ and $a^{10}$.

Best Answer from StackOverflow

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