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

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

• What is the context where you encountered this problem? Can you credit the source where you saw it? What is the motivation? Why is it interesting or useful to others? We're looking to build an archive of knowledge that will be useful to others in the future, so it might help to provide context, motivation, background, etc.
– D.W.
Commented Jul 23 at 19:31

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.

• Two things I don't understand here: first, your definition of $\delta'$ seems to immediately entail that $A'$ is not backward deterministic, since $\delta'(p_i,a)\cap \delta'(q_i,a)\neq \emptyset$. Second, the WLOG part is not that easy if you want to maintain backwards determinism. Commented Jul 24 at 7:53
• yes, backwards determinism means that if two states $p,q$ can lead via letter $a$ to some state $r$, then $p=q$ (i.e., if you reverse the automaton, you'll get a deterministic automaton). Commented Jul 24 at 9:48
• right, the definition by the OP is incorrect in this sense. But I'm fairly sure this is the intention. The "set equivalence" is highly non standard. Commented Jul 24 at 11:19
• @BaderAbuRadi - it seems the OP is satisfied with this. I still think it's a cute problem, and it's puzzling that we don't have an immediate counterexample/proof. Commented Jul 24 at 19:06
• I might have found a counterexample. Wasn't sure if it's appropriate to put here since Dema already accepted an answer, so I've put it here. Commented Jul 25 at 7:39