Routing Automaton

Question

Is there a formal proof for the following question?

For a DFA $M= (Q,\Sigma,\delta,s,A)$, we extend the function $\delta : Q \times \Sigma^* \to Q$, such that every $w \in \Sigma^* $, $\delta(q,w)$ is the individual $q'$ such that $(q,w) \to^*M (q',\epsilon)$. Given a DFA $M= (Q,\Sigma,\delta,s,A)$, we say that a word $w \in \Sigma^* $ is routing in the automaton $M$ if there is a $q \in Q$ such that for every $q' \in Q$ $\delta(q',w) = q$. An automaton $M$ having a routing word, is called a routing automaton.

Prove that every routing automaton $M$ with $k$ states has a routing word of length at most $k^3$.

Hint: what you can say about the length of the words the routes 2 states into a single one?

UPDATE - I think that if i can show that there is a word w, |w| <= $k^2$ that routes 2 states into a single one, then I can build a routing string from this words where the length is at most $k^3$

thanks!

Answer 1

For the hint, suppose that $q, q^\prime \in Q$ are distinct, and $w \in \Sigma^*$ routes $q$ and $q^\prime$ to the same state, that is, $\delta ( q,w ) = \delta ( q^\prime,w )$. If $\mathrm{length}(w) > k^2$, consider the pairs of the form $$\langle \delta (q,w_0) , \delta (q^\prime ,w_0 ) \rangle$$ where $w_0$ is an initial segment of $w$ Note that there are only $k^2$ different pairs of states of $M$, and so there are distinct initial segments $w_0 , w_1$ of $w$ such that $$\delta (q,w_0) = \delta (q,w_1) \;\text{and}\;\delta (q^\prime,w_0) = \delta (q^\prime,w_1).$$ Assuming that $w_0$ is the shorter initial segment, we may write $w$ as $w_0 v u$ where $w_0 v = w_1$. A simple argument will now show that $\delta (q, w_0 u ) = \delta ( q^\prime , w_0 u )$ ($= \delta ( q , w ) = \delta ( q^\prime , w )$).

It follows that if $q,q^\prime$ are states routable to the same state by some word, then there is a word of length $\leq k^2$ which witnesses this (and also attains the same final state).

---

Now suppose that $M$ is routable with final state $p$. Enumerate the other states of $M$ as $\{ q_1 , \ldots , q_{k-1} \}$. We will inductively construct our word $w$ as follows:

• Note that $q_1 , p$ are routable to $p$, and so by the above there is a word $w_1$ of length $\leq k^2$ such that $\delta ( q_1 , w_1 ) = \delta ( p , w_1 ) = p$.
• Note that $q_2^\prime = \delta ( q_2 , w_1 )$ and $p$ are routable to $p$, and so by the above there is a word $w_2$ of length $\leq k^2$ such that $\delta ( q_2^\prime , w_2 ) = \delta ( p , w_2 ) = p$. Note, then, that $\delta ( q_2 , w_1 w_2 ) = \delta ( p , w_1 w_2 ) = p$, and also $\mathrm{length} (w_1 w_2 ) \leq 2 k^2$.
• Continue in this fashion for all the other states of $M$.