Problem Detail: An exercise asks me to show that the Kleene star of any unary language $L$ is regular. $E$ is the alphabet, $E = { 1 }$ Here’s my reasoning :
- $L$ is regular $implies$ $L^*$ is regular (closure property)
- $L$ is not regular
- $L$ contains the word of length 1 $implies$ $L^* = E^* cup {epsilon}$ $implies$ $L^*$ is regular (since $E^*$ is regular, and the union of two regular languages is regular)
- $L$ does not contain the word of length 1 -> … ?
This is where I’m stuck. I don’t know what to do if $L$ does not contain the word of length 1. I do not think that there exists a relation between $L^*$ and $(L text{ complement})^*$. Does anyone have any idea to continue this proof ? Thank you.
Asked By : Martin
Answered By : Shaull
Let $p$ be the $gcd$ of the lengths of all the words in $L$. We claim that there exists $N$ such that for all $n>N$, $1^nin L$ iff $p|n$. Observe that one direction is trivial: $p|n$ for every $1^nin L$ by definition. The converse is less trivial, you can find good guidelines in the answers here Given this claim, you can write $L^*$ as the union of the relevant words up to length $N$, and then $1^{pi}$ for all large enough $i$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10555
