I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string accepted by the DFA. Does anyone know of a "formal" proof that shows this is true in all cases? Guessing induction would be used to prove?

The algorithm goes something like this:

  1. Take original DFA, and change the initial state to the final state
  2. Reverse all accepting states in DFA to non-accepting states
  3. Set original starting state to accepting state and reverse all transitions

Any thoughts would be greatly appreciated!

  • 3
    $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$ – Kaveh Mar 7 '12 at 18:32

If you choose a crisp, symmetric model of NFA $A$ with state set $Q$, where an input symbol maps a subset of $Q$ into another subset of $Q$, with initial and final (accepting) subsets of $Q$, then your sketch is practically a proof. In fact, it will work even if you start, more generally, with an NFA rather than a DFA. (You do have a bit of confusion about final vs accepting states -- they are the same thing, and you'd simply interchange them)

To formalize it, you would indeed use induction to define the transition relation on strings and subsets of states: $\delta (Q_1,xa) = \delta (\delta (Q_1,x),a)$ and the reverse: $\delta_R (Q_2,ax) = \delta_R (\delta_R (Q_2,x),a)$ and show that you get an NFA $A_R$ that accepts exactly the reverses of strings accepted by $A$, the crucial step being that $\delta (Q_1,x)=Q_2 \Leftrightarrow \delta_R (Q_2,x)=Q_1$ for string $x$. Finish by applying that to the initial and final state subsets, which define the language accepted by $A$ and its reverse by $A_R$, string reversal also being given by an inductive/recursive definition.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.