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.
  • 1
    $\begingroup$ Hint: consider cycles in the automaton. $\endgroup$ – Raphael Sep 20 '16 at 8:00
  • 1
    $\begingroup$ Hint: consider cycles in the minimal automaton. $\endgroup$ – Hendrik Jan Sep 20 '16 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.