Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving NFA accepts reverse string of DFA

  1. Mar 7, 2012 #1
    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!
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted