# Reversing a regular deterministic finite automata

• prov
In summary, the algorithm goes something like this:Take original DFA, and change the initial state to the final stateReverse all accepting states in DFA to non-accepting statesSet original starting state to accepting state and reverse all transitionsAny thoughts would be greatly appreciated!
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!

prov said:
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.

Last edited:
prov said:
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.

## 1. What is a regular deterministic finite automata?

A regular deterministic finite automata (DFA) is a mathematical model used to recognize patterns or sequences in a given input. It is a finite state machine that consists of a set of states, a set of input symbols, a transition function, a start state, and a set of accept states.

## 2. What does it mean to reverse a regular deterministic finite automata?

Reversing a regular deterministic finite automata refers to the process of creating a new DFA that recognizes the reverse of the language accepted by the original DFA. This means that the new DFA will accept strings in the reverse order of the original DFA.

## 3. Why is reversing a regular deterministic finite automata useful?

Reversing a regular deterministic finite automata can be useful in various applications such as string matching, pattern recognition, and language translation. It allows for efficient processing of reverse patterns or sequences that may be encountered in real-world scenarios.

## 4. How is a regular deterministic finite automata reversed?

To reverse a regular deterministic finite automata, the states and accept states of the original DFA are swapped, and the direction of the edges is reversed. The start state of the new DFA will be the original accept state, and the accept states will be the original start state and any previous non-accept states.

## 5. Can any regular deterministic finite automata be reversed?

Not all regular deterministic finite automata can be reversed. Only DFAs that accept regular languages can be reversed. A regular language is a language that can be recognized by a DFA. If the original DFA accepts a non-regular language, then it cannot be reversed.

Replies
5
Views
2K
Replies
1
Views
4K
Replies
1
Views
2K
Replies
23
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K