# Finding two words of lengths that are relatively prime in a regular language?

Given a regular language $L$ over a unary alphabet $\Sigma = \{ a \}$.

How to decide whether there are two words $w,w' \in L$ such that the length of $w$ is relatively prime to the length of $w'$ ?

Consider a minimal DFA for $L$. Each state in the DFA has one outgoing edge, so the DFA looks like a path entering a cycle. That means that $W = \{ n : a^n \in L \}$ is eventually periodic: for some $k,l$, for all $n \geq k$ it holds that $n \in W$ iff $n + l \in W$. We are now left with a problem in number theory, which I leave for you to ponder. (Try a few examples to see when an eventually periodic $W$ can fail to satisfy the property you're looking for.)

• Thank you for your hint. Our regular language has additional property: for any words $w \in L$ we have also $w^n \in L$, for all $n \geq 1$. Actually we want to decide existence of $m$ such that all words longer than $m$ are in $L$. Due to your helpful comment we now see that it is equivalent to having a loop in DFA containing only accepting states. – Barbara Sep 4 '13 at 11:28