FOR FREE CONTENT

Example: Reverse of language

 

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

 

Solution:

 

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: