# Effectively compute bound and period of regular expression on single alphabet

It is known that an infinite language $L\subseteq \{a\}^*$ is regular iff the set $U:=\{x|a^x\in L\}$ is ultimately periodic. (A set $U\subseteq\mathbb{N}$ is said to be ultimately periodic if there exists bound, $n$, and period, $p$, such that $\forall x\ge n, x\in U\iff x+p\in U$)

My question is given a finite formalism (DFA, Regular Expression, Regular Grammar, etc.) of an infinite regular language $L$ over $\Sigma=\{a\}$, is the bound $n$ and period $p$ effectively computable? Let us start with regular expression. Suppose we are given the regular expression $R$ of $L$.

What I have thought till now... We will proceed inductively. (Structural induction on $R$)

• If $R=R_1+R_2$ then let $(bound,period)$ of $R_i$ be $(n_i,p_i)$ for $i=1,2$. I claim, for $R$, $n=max(n_1,n_2)$ and $p=lcm(p_1,p_2)$
• If $R=R_1.R_2$ then I claim $(n,p)=(n_1+n_2, p_1+p_2)$
• If $R=(R_0)^*$ then I claim $p=min(U)$ where $U=\{x|a^x\in R_0\}$.

Specific Questions:

1. Are the claims true? What would be a nice formal way to show that?
2. What if the DFA was given? (The period would be something based on the number of states)
3. I also suspect that in item 3 above, even if $R_0$ is not regular, then also $R$ is regular. So the bound and period should be independent on the bound and period of $R_0$, if assumed to be regular.
• Hint: consider cycles in the automaton. – Raphael Sep 20 '16 at 8:00
• Hint: consider cycles in the minimal automaton. – Hendrik Jan Sep 20 '16 at 16:38