1
$\begingroup$

I want to prove: Let $L \subseteq \Sigma^*$.

If $\Sigma=\{a\}$, then $L^*$ is regular.

I found this answer: Kleene star of an infinite unary language always yields a regular language.

But I do not understand the second part of the proof. In the example we should be able to create every word with the length larger then 12 with a combination of $a^4$ and $a^{10}$. But that is not the case e.g. for number 13. Also I do not understand why to multiply with $m^2$ in $m^2 ((\frac{x}{m}-1)(\frac{x}{m}-1)-1)$ and not just with $m$ to scale it back up.

$\endgroup$

1 Answer 1

2
$\begingroup$

That is not what the last paragraph says. The last paragraph says "we know that we can get any word whose length is multiple of $m$ if ..". In the example, $m=2$, so you should not expect to be able to get $a^{13}$.

The last paragraph stated a fact (the one about length greater than $m^2[\cdots]$). It did not explain why that fact is true. So you should not expect to understand why that fact is true, or why it contains the particular expression it does as opposed to some other expression. The way to find out why it is true is to seek a proof of that fact.

Before you do that, make sure you understand the first paragraph, and especially the fact about lengths greater than $(x-1)(y-1)-1$. If you cannot prove that fact, then study that first.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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