Around Don’s Conjecture for Binary Completely Reachable Automata

A word w is called a reaching word of a subset S of states in a deterministic finite automaton (DFA) if S is the image of the whole state set under the action of w. A DFA is called completely reachable if every non-empty subset of the state set has a reaching word. Don’s conjecture states that in every n-state completely reachable DFA, for every s-element subset of states, there exists a reaching word of length at most \(n(n-s)\) . We present infinitely many completely reachable DFAs with two letters that violate this conjecture when \(s = n-2\) . A subfamily of completely reachable DFAs with two letters, called standardized DFAs, was introduced by Casas and Volkov (2022). We prove that every s-element subset of states in an n-state standardized DFA has a reaching word of length \(\le n(n-s) + n - 1\) . Finally, we confirm the conjecture for standardized DFAs with additional properties, thus generalizing a result of Casas and Volkov (2023).