Proof that its possible to generate NFA from DFA

[prov]

Homework Statement

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.

Homework Equations

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!

 

[KataKoniK]

Hello,

Thank you for sharing your algorithm and inductive hypothesis. Your approach seems to be on the right track. To prove your algorithm, you will need to show that it works for all possible inputs, not just the base case of ε.

One way to do this is to use strong induction, as you mentioned. In your inductive step, you will assume that your algorithm works for all strings of length n-1 and show that it also works for strings of length n. This will require you to consider all possible transitions and states in the DFA and NFA.

To prove the other direction, you can use a similar approach. Assume that the reverse of w is accepted by the NFA and show that the DFA accepts w. This will also require considering all possible transitions and states in both the DFA and NFA.

It may also be helpful to use a proof by contradiction, where you assume that your algorithm does not work and then show that this leads to a contradiction. This can help you identify any potential flaws in your algorithm and strengthen your proof.

I hope this helps guide you in your proof. Let me know if you have any further questions or need any clarification. Good luck!