3
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by Ran G., Kaveh, vonbrand, JeffE, Paresh Mar 17 '13 at 9:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from cstheory.stackexchange.com Mar 16 '13 at 18:41

This question came from our site for theoretical computer scientists and researchers in related fields.

3
$\begingroup$

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^n\in L$ iff $p|n$.

Observe that one direction is trivial: $p|n$ for every $1^n\in 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$.

$\endgroup$

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