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!