1
$\begingroup$

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?

$\endgroup$
  • $\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$ – Abdous Kamel Nov 24 '17 at 13:30
  • $\begingroup$ The comment refers to a deleted comment. I have now deleted my own comment as well. $\endgroup$ – Yuval Filmus Nov 24 '17 at 15:26
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is there an easier way to do this without considering cyclic permutations? $\endgroup$ – Krish__ Nov 24 '17 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$ – Yuval Filmus Nov 24 '17 at 15:31

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.