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