How do I prove a DFA has no synchronizing word?

Question

To find a synchronizing word I have always just used trial and error, which for small DFAs is fine but not so useful on larger DFAs. What I want to know, however, is if there exists an algorithm for determining a synchronizing word or if there is a way of being able to tell that one does not exist. (Rather than just saying "I can't find one, therefore one can not exist" which is by no means a proof).

I have had a look around on google and so far just came across methods for determining what the upper and lower bounds for a length of a synchronizing word would be based on the number of states, however this is not helpful to me.

Answer 1

The existence of upper bounds on the length of a synchronizing word immediately implies the existence of a (very slow) algorithm for finding one: just list all strings of length less than the upper bound and test whether each is a synchronizing word. If any of them are, then the synchronizing word exists, and if none of them are, there's no synchronizing word. This is exponentially slow, though, so it's not advisable on large DFAs.

David Eppstein designed a polynomial-time algorithm for finding synchronizing words in DFAs, though I'm not very familiar with this algorithm.

Hope this helps!