(adsbygoogle = window.adsbygoogle || []).push({}); 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!

**Physics Forums | Science Articles, Homework Help, Discussion**

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

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**