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**

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**