# Synchronizing sequence and Synchronizable DFA

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$$. Moreover, can you improve upon this bound?

I'm more interested in proving that the synchronized sequence is of length of at most $$k^3$$ then trying to improve upon this bound.

I tried to prove (with no success) that there exists $$w\in \Sigma^*$$ which $$|w| \leq k^2$$ so that: $$\delta(q_1,w)=\delta(q_2,w)$$ for two distinct states in $$M$$: $$q_1,q_2\in Q$$ (thus, $$w$$ can be read from two states in the automaton and get to the same final state).
If I prove it, I could construct a word $$w$$ which will be a synchronizing sequence in $$M$$ and $$|w|\leq k^3$$ as required.

Any suggestions?

• Finding the best upper bound on the length of a synchronizing sequence is a famous open problem. It has been conjectured by Cerný in 1964 that the best upper bound is $(k-1)^2$ but the best known upper bound is ${1\over 6}(k^3-k) -1$. See this survey for more details. Cerný's conjecture is one of the oldest open problems in automata theory. – J.-E. Pin Dec 7 '13 at 9:48

Consider two states $q_1,q_2$. We claim the following:
If there exists a word $w$ such that $\delta(q_1,w)=\delta(q_2,w)$, then there is such a word $w$ of length at most $k^2$.
The proof of this a standard shrinking argument: if such a word is longer than $k^2$, then during the runs from $q_1,q_2$, a pair of states repeats, and we can shrink $w$.
• @scaaahu There should be a state $q'$ called "home" which is the final state for every $q\in Q$, so that $\delta(q,w)=q'$ for a synchronizing sequence $w$ which fits $q'$ in $M$ – user11841 Dec 7 '13 at 15:21