Suppose $M=(Q,\Sigma,\delta,q_0,F)$ is a deterministic finite automaton, and suppose there exists a state $q \in Q$, a string $z \in \Sigma$, and integers $i,j>0$ such that $\delta(q,z^i)=\delta(q,z^j)=q$. Prove that $\delta(q,z^{gcd(i,j)})=q$

I can intuitively say that starting from a state $q$ if you take $x$ steps on a DFA to reach the same state and at the same time $y$ steps also takes the DFA to the same state, then there exists a cycle that is repeated $\gcd(x,y)$ times to reach the same state again and again. Is this correct for a DFA? How can I prove this formally?

  • $\begingroup$ @ratchetfreak For the language that you gave, you must consider a DFA that recognize it, not the language itself. The claim talks about implementations, not semantic. $\endgroup$
    – user80502
    Nov 24, 2017 at 13:30
  • $\begingroup$ The comment refers to a deleted comment. I have now deleted my own comment as well. $\endgroup$ Nov 24, 2017 at 15:26

1 Answer 1


Consider the sequence $q(n) = \delta(q,z^n)$ for $n \geq 0$. Let $b$ be the smallest index so that $q(a) = q(b)$ for some $a < b$. It is not hard to check that all further iterates cycle through the values $q(a),\ldots,q(b-1)$. Since we are given that $q(i) = q(0)$, it follows that $a = 0$, and so the function $\pi$ on $\{q(0),\ldots,q(a-1)\}$ defined by $\pi(q') = \delta(q',z)$ is a cyclic permutation.

We are given that $\pi^i(q) = \pi^j(q) = q$. Since $\pi$ is a permutation, also $\pi^{-i}(q) = \pi^{-j}(q) = q$. It follows that for any integer $\alpha,\beta$ (not necessarily non-negative) $\pi^{\alpha i + \beta j}(q) = q$. In particular, Bezout's identity shows that $\pi^{\operatorname{gcd}(i,j)}(q) = q$, and so $\delta(q,z^{\operatorname{gcd}(i,j)}) = q$.

  • $\begingroup$ Is there an easier way to do this without considering cyclic permutations? $\endgroup$
    – Krish__
    Nov 24, 2017 at 15:29
  • $\begingroup$ I don't think so, though there may be other ways to formulate the same idea which you might like better. The crux of the matter is that you can go not only "forward" but also "backward". $\endgroup$ Nov 24, 2017 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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