Reversing a regular deterministic finite automata

[prov]

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!

 

[SW VandeCarr]

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.

 

[andrewr]

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!

I build almost exclusively DFA's; NFA's tend to be compiled into DFA's for things such as lexical analysis (see Bison, Lex ) for example. An NFA is something typically used to do regular expression matching: say "(A|B|C)*C"; In this type of regular expression any number of items like "ABCBCBAB" may occur before a final character "C"; so it is obvious that the automaton is halted by an external signal which marks "end of string", otherwise the NFA could not know the difference between a non final "C" and a final one. To convert such an NFA into a DFA automaton -- one simply adds to the transition condition whatever implied external signal is needed: eg for the case above the last transition, to the accepting state is: (input="C" & "Last Character"), and to guide a non-final "C", the external trigger is inverted: eg: (input="C" & not "Last Character");

So, your question amounts to being able to build a deterministic finite automaton, with external signals applied to decide which of multiple transition trigger conditions is to be taken; Since the original automaton may traverse many paths to a "same" accept state, it can have a "many" to "one" type of mapping to the final state; Therefore, in order to reverse a many-to-one DFA, exactly, one has to know which of the "one to many" is to be choosen in a reverse transition; That's a problem in practice...

Correct choice of "one" to "many" is not always possible unless the selection of a particular transition is known by an implied external piece of evidence; But that is tantamount to saying -- you can always build a reversing "NDA", so long as the implied way of selecting a reverse transition has knowledge of the exact string being generated; in practice, this is called cheating...

If you already know the string being supposedly "generated", and use it to decide how to go "from one state to one of many states" then you essentially are doing nothing more than copying the string...!; It "IS" possible to do this, so the NFA does exist -- but it really cheating --

Moving on to a different point: In some very simple DFA, where there is never a many to 1 mapping, a non-degenerate reverse DFA is possible (eg:without fore-knowledge), and therefore so is an NFA.

Between these two extremes, there is a middle ground.
You can make a NFA that copies on certain transitions from certain states, but which is deterministic at other states -- and therefore doesn't "always" need to cheat / copy.
If cheating is sometimes allowed, then the idea presented for the reversing algorithm can be made to work.

Hopefully, these caveats will help you build your inductive proof... :)