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.


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

| cite | improve this answer | |
  • 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$ – David Richerby Apr 21 '17 at 8:39
  • 1
    $\begingroup$ thanks a lot, was wondering if it is possible to use lateX on this site $\endgroup$ – Nikolskyy Apr 22 '17 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$ – Agnishom Chattopadhyay Oct 20 '17 at 16:11

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.