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!