5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – J.-E. Pin Dec 7 '13 at 9:48
2
$\begingroup$

I think you are on the right track:

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

Now, since you assume the existence of a synchronizing word for all states, you can proceed to construct a word that synchronizes all the states, pair by pair.

$\endgroup$
  • $\begingroup$ Am I right by saying this problem has nothing to do with final states? If so, why am I seeing mention of final states in the question? $\endgroup$ – scaaahu Dec 7 '13 at 4:25
  • 1
    $\begingroup$ @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$ $\endgroup$ – user11841 Dec 7 '13 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy