I am trying to prove problem 1.59 in Sipser's book: Introduction to the theory of computation , 2nd Edition.

Let $M=(Q,\Sigma,\delta,q_0,A)$ be a DFA and let $q'$ be a state of $M$ called its "home". A Synchronizing sequence for $M$ and $q'$ is a string $s\in \Sigma^*$ where $\delta (q,s)=q'$ for every $q\in Q$. (We actually have extended $\delta$ to strings so that $\delta(q,s)$ equals the state where $M$ ends up when $M$ starts at state $q$ and reads input $s$).

Say that $M$ is Synchronizable if it has a synchronizing sequence for some state $q'$.

Prove that, if $M$ is a $k$-state synchronizable DFA, then it has a synchronizing sequence of length at most $k^3$.

This problem was already attempted here. I don't understand the answer though:

The proof of this a standard shrinking argument: if such a word is longer than $k^{2}$, then during the runs from $q1$,$q2$ a pair of states repeats, and we can shrink $w$.

How come a pair of states repeats?

I don't see a problem with runs from $q1$ and $q2$ reaching separate states. I don't so how I could be sure that I could shrink to word without disturbing both routes.


1 Answer 1


synchronously moving through the DFA beginning with two different states while an input of a word w can be described as choosing two states out of k on every step. So there exist $\binom{k}{2}$ possibilities to do that. As $k^2>\binom{k}{2}$, there will be one step where we choose a pair of states which we already had before. So the word $w$ can be shortened: this is the contradiction to the claim that the word is longer then $k^2$.

  • 1
    $\begingroup$ Welcome to the site! Note that "$k$ over $2$" means $k/2$, not $\binom{k}{2}$. I edited your post to correct this. $\endgroup$ Apr 21, 2017 at 8:39
  • 1
    $\begingroup$ thanks a lot, was wondering if it is possible to use lateX on this site $\endgroup$
    – Nikolskyy
    Apr 22, 2017 at 19:26
  • $\begingroup$ This proves that given any two states, if there is a synchronizing sequence that works for them, there is such a sequence of length $q^2$. But why should the same word work for every two pair? $\endgroup$ Oct 20, 2017 at 16:11

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.