A string that takes a DFA from any state to a given state?

Question

EDIT: as templatetypedef commented, this problem is to find out if a DFA has a synchronizing word (a.k.a. "reset sequence").

Given a finite state set $Q$, a finite alphabet $\Sigma$, and a transition function $\delta : Q \times \Sigma \rightarrow Q$, I want to find out if there is a state $q_f \in Q$ and a string $s \in \Sigma^*$ such that for every state $q_0 \in Q$ (including $q_f$), the DFA $\left( Q, \Sigma, \delta, q_0, \left\{ q_f \right\} \right)$ accepts $s$. ($q_0$ is the initial state; $q_f$ is the only accepting state.)

In other words, if you think of a string as a list of directions for navigating the DFA, I want to find out if there is a list of directions that takes you to the same state no matter where you started. (Knowing the existence is enough; I do not need to know the state or the string itself.)

I have tried this algorithm:

1. Reverse the transitions in $\delta$ to form an NFA.

2. Convert the NFA into a DFA where each state corresponds to a subset of the NFA's states.

3. For each state $q \in Q$, search the new DFA for a path from $\left\{ q \right\}$ to $Q$. (I just do a depth first search.)

4. Iff one of these searches is successful, then the answer to the question is "yes".

This algorithm is correct, but it runs in exponential time and space, and it takes too long to complete. (My input DFAs have tens of states.) Note that I do not actually construct a DFA from the NFA -- instead, I perform the search on the NFA and I remember which subsets of its states I have visited.

Is there a way to improve my algorithm? Are there other algorithms to solve this problem? (Or at least, algorithms that would be useful?) Are there any properties of automata and regular languages that I can take advantage of?

Answer 1

It turns out that there exists a string that takes all states to the same state iff for each pair of states, there exists a string that takes both states to the same state.

Using this fact, I had success with the following algorithm:

• Generate a new DFA from the Cartesian product of the old DFA with itself. (The new DFA contains $\left(a,b\right) \overset{x}{\rightarrow} \left(c,d\right)$ iff the old DFA contains $a \overset{x}{\rightarrow} c$ and $b \overset{x}{\rightarrow} d$, where $x$ is an input symbol and $a$, $b$, $c$, and $d$ are states.)
• For each state $\left(a,b\right), a \neq b$ in the new DFA, search for a path from $\left(a,b\right)$ to a state of the form $\left(c,c\right)$. (If found, then that means there is a string that takes the old DFA from $a$ to $c$ and from $b$ to $c$.)
• There is a reset sequence for the old DFA iff every search in the above step yields such a path.

More info:

https://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-90.pdf