# Determining whether $L^*$ is a finite union of $L^n$ for unary regular $L$

Give an algorithm that, given an NFA over a one-letter alphabet, determines whether the language it generates has the property that for some $n$, $$L^* = \bigcup_{k=0}^n L^k.$$

I need some tips how to solve that.

• What is $L$? Should it be $L^k$ (without braces) instead of $\{L^k\}$? May 18, 2018 at 18:06

We can identify every unary regular language $L$ with the set $S = \{ n : 1^n \in L \}$. It is known that $S$ is eventually periodic, that is, $$S = A \cup (B + m \mathbb{N}) = A \cup \{ b + mn : b \in B, n \in \mathbb{N} \}$$ for some finite $A,B$ and $m \geq 1$. Let us consider four cases:
Case 1. $S$ is empty. In this case, $S^* = S^0$.
Case 2. $S$ is finite and non-empty. In this case, $S^*$ is infinite but $S^0 \cup \dots \cup S^n$ is finite for all $n$.
Case 3. $S = B + m\mathbb{N}$ for some non-empty $B$ and $m \geq 1$. I claim that $$B^* \bmod{m} = (B^1 \cup \dots \cup B^\ell) \bmod{m}$$ for some finite $\ell$. Indeed, if $i \in B^* \bmod{m}$ then $i \in B^j \bmod{m}$ by definition of $B^*$ for some $j \geq 1$ (when $i = 0$ we can take $j = m$), so we can take $\ell$ to be the maximum of the $j$'s. It follows that $$S^+ = \bigcup_{i \in B^* \bmod m} n_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m}, \\ S^1 \cup \cdots \cup S^\ell = \bigcup_{i \in B^* \bmod m} n'_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m},$$ where $n'_i \geq n_i$. It follows that $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ is finite, and so $S^* = S^0 \cup \cdots \cup S^r$ for some finite $r \geq \ell$, since every element in $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ appears in some $S^j$.
Case 4. $S = A \cup (B+m \mathbb{N})$ for some non-empty $A,B$ and $m \geq 1$. Let $C = A \cup B$. As before, $$C^* \bmod m = (C^0 \cup \cdots \cup C^\ell) \bmod m$$ for some finite $\ell$. Since $B$ is non-empty, $(B+m \mathbb{N})^m$ contains some multiple of $m$, and so all large enough multiples of $m$. Assuming $\ell \geq m$, it follows that $$S^* = D \cup \bigcup_{i \in C^* \bmod m} n_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m}, \\ S^0 \cup \cdots \cup S^\ell = D' \cup \bigcup_{i \in C^* \bmod m} n'_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m},$$ where $D \supseteq D'$ are finite and $n'_i \geq n_i$. It follows that $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ is finite, and so $S^* = S^0 \cup \cdots \cup S^r$ for some finite $r \geq \ell$.
Conclusion. The property $S^* = S^0 \cup \cdots \cup S^n$ holds for some finite $n$ unless $S$ is finite and non-empty. Given a finite automaton for $L$, this condition is easy to check (in linear time).