# 22.6 Completing Partial DFAs to Synchronizing DFAs

Problem Definition: Let $$A = (Q, \Sigma, \delta)$$ be a (complete) deterministic finite automaton (DFA) where $$Q$$ is a finite set of states, $$\Sigma$$ is a finite alphabet and $$\delta \colon Q \times \Sigma \to Q$$ is a (totally defined) transition function (we neglect start and final states). We generalize $$\delta$$ to words $$w= w_1w_2 \dots w_n$$, $$w_i \in \Sigma$$ by setting $$\delta(q, w) = \delta(\delta(q, w_1)w_2\dots w_n)$$. We further generalize it to sets $$S$$ of states by $$\delta(S, w) = \cup_{q\in S}\{\delta(q, w)\}$$. We say that a word $$w\in \Sigma^*$$ is synchronizing for $$A$$ if $$|\delta(Q, w)| = 1$$, i.e., regardless from which state we read $$w$$, we end up in the same state.

We call a DFA partial, if $$\delta$$ is a partial function. For a partial DFA $$A$$, we call a word $$w\in \Sigma^*$$ carefully synchronizing, if $$|\delta(Q, w)|=1$$ and $$\delta(q, w)$$ is defined fore each $$q\in Q$$, i.e., we never try to use an undefined transition when reading $$w$$ from any state.

The problem of DFASyncCompletion asks, given a partial DFA $$A=(Q, \Sigma, \delta)$$, is there a complete DFA $$A'=(Q, \Sigma, \delta')$$ such that $$A'$$ is synchronizing and $$\delta \subseteq \delta'$$?

Open Question: What is the complexity of DFASyncCompletion?

Explanation & Comments: Finding a synchronizing word for a complete DFA can be done in polynomial time, but finding a carefully synchronizing word for a partial DFA is PSPACE-complete.