2
$\begingroup$

I'm trying to prove the if $𝑀$ is a $𝑘$-state synchronizable DFA, then it has a synchronizing sequence of length at most $𝑘^3$. first I have to prove that if a string syncs two states, then its length is at most $k^2$.

The question was answered here.

The proof of this a standard shrinking argument: if such a word is longer than $𝑘^2$, then during the runs from $𝑞_1,𝑞_2$, a pair of states repeats, and we can shrink $𝑤$.

But how to know if the repeating string in both paths from $𝑞_1,𝑞_2$ to some states like $q_i$ is the same? and shrinking the string won't damage the synchronization?

To make it more clear I drew the below picture.

enter image description here

The string $abcd$ takes $𝑞_1,𝑞_2$ to $q_i$ but after eliminating the loops, string $acd$ takes $𝑞_1$ to $q_i$ and string $abd$ takes $𝑞_2$ to $q_i$, thus removing the loops will break the synchronization.

Any suggestions would be greatly appreciated, thanks.

Edit: This is the visualisation I drew from Hendrik Jan's helpful answer:

Consider two arbitrary states $q_1$ and $q_2$ where $𝛿(q_1, w)=𝛿(q_2, w)=q_i$.

Suppose $|w|=k,\ w=v_1…v_k$ then: enter image description here The loop happens when $𝛿((q_1^j, q_2^j),\ v_{j+1})=(q_1^i, q_2^i)$.

$\endgroup$

1 Answer 1

3
$\begingroup$

I am afraid that "a pair of states repeats" is a little ambiguous.

Both computations (from $q_1$ and $q_2$) have to be considered in parallel. So we get a pair of "synchronized" computations $(q_1,q_2), (q^1_1,q^1_2), (q^2_1,q^2_2), \dots, (q_i,q_i)$. If in such a sequence-pair a state-pair repeats we can remove the sequence in between (from both components).

That is also consistent with the $k^2$ bound, as that is the total number of state pairs.

$\endgroup$
1
  • $\begingroup$ This was very helpful! thanks. I would upvote but my reputation won't let me :) $\endgroup$
    – ladypary
    Jun 16, 2021 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.