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

Homework Help: Proof that its possible to generate NFA from DFA

  1. Mar 7, 2012 #1
    1. The problem statement, all variables and given/known data
    I am attempting to prove the following:

    For a determenistic finite automata D = (Q, Ʃ, ∂,q0,A) that accepts w, prove that a nondeterministic finite automata can be generated to generate the reverse string of w.

    2. Relevant equations

    3. The attempt at a solution

    I have figured out a general algorithm that works like so:
    1. change the initial state to the final state in the DFA
    2. Reverse all accepting states in DFA to non-accepting states
    3. Set original starting state to accepting state and reverse all transitions

    Now I need to prove this. It seems a strong induction proof will be required. I have setup the following inductive hypothesis: If string w is accepted by the DFA and the length of w = n, then w reverse can be generated from the NFA created from the algorithm above.

    For my base case I use n = 0, which is ε ( sometimes noted as λ or empty string). The reverse of ε is ε which can be accepted by both the DFA and NFA above.

    I am a bit confused where I need to go from here. Also, since I am using induction, I will need to prove the other direction as well, that is if the reverse of w is accepted by the NFA, the DFA accepts w. I don't quite understand how this will be much different than the first direction.

    Any and all help is 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