Example: Reverse of language


Q. Consider a language L= {a*b*}. Find the reverse of the language. 




First design machine of a*b*   (For detailing of this machine design follow Chapter DFA/NFA machine design)



Taking reverse of machine M: Change all final states to starting states and starting state to final. And reverse arrows with the same level



Here are two starting states so, it is transition diagrams. So, we convert it to Finite State Machine.


Note: More than one starting state is treated as a transition diagram not a Finite State Machine.


Converting Transition diagram to Finite State Machine


We can convert it by two λ moves and make one initial state, i.e. λ – moves do not change machine’s power so, we can add λ – moves.


We can remove dead state



Now, reverse of the given language: