Is there an algorithm to turn any finite automata into a backwards deterministic one, with no $\epsilon$ transitions, and only one initial state?

Question

An automaton is backwards deterministic if, for all states q, p, for all symbols a: $$ (\delta(q, a) = \delta(p, a)) \implies p = q $$

(I think the right translation is backwards deterministic, but english isn't my main language so please correct me if it's wrong)

If you reverse it, determinize it, and reverse it again, you might get $\epsilon$-transitions from the initial state (or multiple initial states), to the ones that were final in the reversed automaton, and I couldn't find a way of removing them without breaking backwards determinism

I tried other methods, like iteratively removing each "backwards determinism conflict", but they end up breaking when you get to the initial state, you eventually need $\epsilon$-transitions.

I'm not sure such an algorithm is possible

Answer 1

I might be missing something, but it seems to me like this can be done by simply adding superfluous states. So if $\delta(p, a) = \delta(q, a)$ for some $a$ you add a new state $r$ and add it to $\delta(p, a)$. You just have to be careful that these additional states don't break backwards determinism.

---

Assume that $A = (\Sigma, Q, q_0, \delta, F)$ is a NFA without $\varepsilon$-transitions. Additionally assume WLOG that $\delta(q, a) \neq \emptyset$ for all $q \in Q$, $a \in \Sigma$. Define a NFA $A' = (\Sigma, Q', q_0, \delta', F)$ such that

• $Q' = Q \cup \{p_1, p_2, ..., p_n\}$ for $Q = \{q_1, q_2, ..., q_n\}$,
• $p_i \notin Q$ for $1 \leq i \leq n$, and
• $\delta'(p_i, a) = \{p_i\}$ as well as $\delta'(q_i, a) = \delta(q_i, a) \cup \{p_i\}$ for all $a \in \Sigma$.

It can easily be seen, that none of the $p_i$ are part of an accepting computation. So you can verify that $L(A) = L(A')$. Notice that for $a \in \Sigma$

• $|\delta'(q_i, a)| > 1 =|\delta'(p_i, a)|$ for all $i,j$,
• $p_i \in \delta'(q_i, a)$ and $p_i \notin \delta'(q_j, a)$ for all $i \neq j$, and
• $\delta'(p_i, a) = \{p_i\} \neq \{p_j\} = \delta'(p_j, a)$ for $i \neq j$.

Thus $A'$ is also backwards deterministic.