L $ \subseteq \{a\}^* $ => $L^*$ is regular

Question

I having trouble showing that if $L \notin REG $ => $ (L^*)= \hat L \in REG $.

I know that if $ | \Sigma/ \sim_\hat L | < \infty => L \in REG $ so there must be a way to tell if w $ \in \{a \}^* $ is in one of the classe $[a]_{\sim_\hat L} $ = {w $ \in \{ a\}^* | a \sim_\hat L w $}.

Can you help me proofing this Lemma ?

Answer 1

Hint:

• Because $L \subseteq \{\mathtt{a}\}^*$, the only thing that matters are the lengths of words.
• In fact, we only care about lengths after we cut off an arbitrairly long initial segment (because any finite subset of $\{\mathtt{a}\}^*$ is regular).
• WLOG we can assume $\varepsilon\notin L$ (the empty word does not change anything for $L^*$).
• Let $\mathtt{a}^n$ be the shortest word in $L$. Now consider lengths of words of $L^*$ modulo $n$. We set $w_0 = \mathtt{a}^n$, and define $w_i$ as the shortest word of $L^*$ which length is $i$ modulo $n$ or the empty word if no such word belongs to $L^*$, i.e. \begin{align*}A_i &= \{k\in\mathbb{N}\mid \mathtt{a}^k\in L^*, k\bmod n= i\}\\w_i &= \begin{cases}\mathtt{a}^{\min A_i}&\text{ if } A_i\neq\varnothing\\\varepsilon&\text{ otherwise}\end{cases}\end{align*}
• Prove that for some finite language $I$ we have $L^* \subseteq I\cup\{w_0,w_1,\ldots,w_{n-1}\}^*$.

I hope this helps $\ddot\smile$