Reverse of grammar:


Reverse of grammar and machine


We did a complement of the machine in the previous chapter  Design a DFA for Language.


But complement of the machine and the reverser of the machine is not the same concept.


Complement of  the machine: 


1. Non-final states will be final states

2. Final states will be non-final states



Reverse of  the machine: 


  1. Exchange initial state and final state [all final states will be starting states and starting state will be final]
  2. Reverse all the arrows in which levels as it is.
  3. Keep self-loop as it is.


Now how we take the reverse of a machine:



Reverse of the grammar:



Reverse of the grammar means reverse of language. 


Let consider a grammar G which generate a language L = {ab, abb}


Now reverse of the grammar (GR) = reverse of language LR  = {ba, bba}


How we do the reverse of the grammar:


1. First we design a machine M of the grammar G.

2. Take a reverse (MR) of the machine M.

3. Construct grammar GR from reverse machine MR.


Now, this GR is reverse of the grammar G.






We can remove trap state.



Equivalent grammar, 



Reverse of machine M:




Trap state B convert it to dead state at MR.


Reverse of the grammar 




And the language of this grammar is: