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.)

  • 1
    $\begingroup$ 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. $\endgroup$ – Barbara Sep 4 '13 at 11:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.