View Single Post
SW VandeCarr
Mar7-12, 06:32 PM
P: 2,500
Quote Quote by prov View Post
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:

Take original DFA, and change the initial state to the final state
Reverse all accepting states in DFA to non-accepting states
Set original starting state to accepting state and reverse all transitions
Any thoughts would be greatly appreciated!
In the normal forward process, is there a choice point at each step? How is the choice made? In a Markov process, the choices are weighted by probabilities such P(A)= x and P(B)= 1-x (if there are only two choices and 1>x>0). A Markov process is probabilistic. If you reverse it, it might be deterministic if the nature of the program is for the return path to follow the outward path back to its original initial state. On the other hand, if the outward path is fully determined, I don't see how the return path can be probabilistic unless programed to be so. This can't be done simply by reversing the original program afaik.