Question

Let $\mathit{M}\mathbf{=}\left(Q,\Sigma ,\delta ,q_0,F\right)$be a DFA and let be a state of Mcalled its “home”. A synchronizing sequence for M and h is a string s∈Σ∗where$\mathit{\delta }\left(q,s\right)\mathbf{=}\mathit{h}\mathit{f}\mathit{o}\mathit{r}\mathit{e}\mathit{v}\mathit{e}\mathit{r}\mathit{y}\mathit{q}\mathbf{\in }\mathit{Q}\mathbf{.}$ (Here we have extended to strings, so that$\mathit{\delta }\left(q,s\right)$ 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 $\mathbf{k}\mathbf{-}$state synchronizable DFA, then it has a synchronizing sequence of length at most${\mathbf{k}}^3$ . Can you improve upon this bound?

Short answer

Step by Step Solution:

Step-by-step solution

Synchronizable DFA.

A synchronizing word or reset sequence is a word in the input alphabet of the deterministic finite automata that sends any state of the deterministic finite automata to one and the same state. That is, if an ensemble of copies of the deterministic finite automata are each started in different states, and all of the copies process the synchronizing word, they will all end up in the same state. Not every deterministic finite automata has a synchronizing word; for instance, a deterministic finite automata with two states, one for words of even length and one for words of odd length, can never be synchronized.

Proof of statement.

Here as from the question$M=\left(Q,\Sigma ,\delta ,q_0,F\right)$be a deterministic finite automata and h be a state of M called its “home”.

And a synchronizing sequence for M is given.Let$M=\left(Q,\Sigma ,\delta ,q_0,F\right)$be a deterministic finite automata and let $q\text{'}$be a state of M called its "home".

A Synchronizing sequence for M and $q\text{'}$is a string $s\in \Sigma *$ where $\delta (q,s)=q\text{'}$for every$s\in \Sigma *$(We actually have extended $\delta$to strings so that $\delta (q,s)$equals the state where M ends up when M starts at state and reads input).

Say that M is Synchronizableif it has a synchronizing sequence for some state$q\text{'}$.

M' more interested in proving that the synchronized sequence is of length of at most then trying to improve upon this bound. There exists

In which$\left|w\right|⩽k^2\left|w\right|⩽k^{2}sothat:\delta (q_1,w)=\delta (q_2,w)\delta \left(q_1,w\right)=\delta \left(q_2,w\right)$ for two distinct states in M : (thus, M 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 M which will be a synchronizing sequence in M and $\left|w\right|⩽k^3$ as required.

Consider two states and then claim the following:

If there exists a word ww such that $\delta \left(q_1,w\right)=\delta \left(q_2,w\right),$ then there is such a word 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 two states a pair of states repeats, and we can shrink w.

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