2

From Sipser's book:

Let $M=(Q,\Sigma,\delta,q_0,A)$ be a DFA and let $h$ be a state of $M$ called its "home". A synchronizing sequence for $M$ and $h$ is a string $s\in \Sigma^*$ where $\delta (q,s)=h$ 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 $h$.

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 am focused on proving the $k^3$ bound.

Preliminary findings: The DFA M, given that it is synchronizable, cannot have more than one absorbing state and if it indeed has one, the "home" state cannot be anything other than that absorbing state. But how do I go about proving the $k^3$ bound? My gut feeling tells me to use induction, yet I cannot find a recursive structure. This problem was also posted in the CS forum some time ago, but I did not gain further insight from that discussion.

Community
  • 1
Vectorizer
  • 833
  • A synchronizable DFA does not have necessarily an absorbing state. – J.-E. Pin Jan 13 '16 at 15:24
  • @J.-E.Pin: Thanks for your input. "...cannot have more than one absorbing state and if it indeed has one, the "home" state cannot be anything other than that absorbing state." I am not claiming that it has to have one; it can only have 0 or 1 absorbing state. And if it happens to have one, the "home" state has to be that absorbing state. – Vectorizer Jan 13 '16 at 15:39
  • Actually, if a synchronizable DFA has an absorbing state, the bound $k^3$ can be improved to a quadratic bound. – J.-E. Pin Jan 13 '16 at 16:03

1 Answers1

1

Notation. Let $|S|$ denote the number of elements of a finite set $S$. Let $Q$ be the set of states of the automaton. Given $S \subseteq Q$ and $u$ a word, let $Su = \{ q\cdot u \mid q \in S \}$.

Hint. Let $S \subseteq Q$ with $|S| \geqslant 2$. Show that there exists a word $u$ of length $\leqslant k^2$ such that $|Su| < |S|$.

J.-E. Pin
  • 40,163
  • Not really sure about the meaning of Su={q⋅u∣q∈S}; are you applying an input sequence (word u) to a state q? – Vectorizer Jan 13 '16 at 15:44
  • Yes, if you prefer, $q\cdot u$ is the state reached after reading $u$ from state $q$. – J.-E. Pin Jan 13 '16 at 15:49
  • As I started looking at papers on the subject, your name came up quite often. Thank you for your responses, it is an honor for me. – Vectorizer Jan 13 '16 at 22:06