Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.