1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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