- #1

prov

- 3

- 0

## 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!