Reversal of DFA

Question

When reversing a DFA, if there are more than one final states in initial DFA then after reversing it how to decide which state to declare the start state of reversed FA

Comments

check it

https://www.google.co.in/search?q=reversing+a+DFA&ie=utf-8&oe=utf-8&gws_rd=cr&ei=U8KVV7zaL4-UvQSt2K-wBg

Answer 1

If there is only one final state in initial DFA then, simply make that final state to initial state and initial state to final state and reverse all the transition. But, If there are more than one final states in initial DFA then, then the problem is that in reverse DFA there are more than one initial states which can't possible, For this:- consider an extra state and make e (epsilon) transition from it to all states which are final states in initial DFA and rest are same as above. And to obtaiin DFA convert it to DFA.

Answer 2

If there are multiple final states in DFA then create a new final state and make epsilon transitions to this new state from all final states. The rest of the procedure remains same.

Comments

but that would make the dfa to nfa .. becuase dfa dont have eplison moves right...

---

@arunsingh

Reversal of a DFA does not necessarily give a DFA, it may result in a NFA too.

Answer 3

whenever you take compliment of DFA one thing should be remember that is final state change into nonfinal & non final state change into final state.
for taking compliment of DFA start state is same as initial DFA which means no change in start state.

Comments

Complement is not same as reverse.

---

sry sir i getting this point. in reverse direction is also change but sir for initial state is there is more then one initial state are possible if we not including epsilon transitions???