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?(adsbygoogle = window.adsbygoogle || []).push({});

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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Proving NFA accepts reverse string of DFA

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**