CREATE OWN LIBRARY

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:

Exchange initial state and final state [all final states will be starting states and starting state will be final]
Reverse all the arrows in which levels as it is.
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 $(G^{R})$ = reverse of language $L^{R}$ = {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 $(M^{R})$ of the machine M.

3. Construct grammar $G^{R}$ from reverse machine $M^{R}$ .

Now, this $G^{R}$ is reverse of the grammar G.

Example:

We can remove trap state.

Equivalent grammar,

Reverse of machine M:

Trap state B convert it to dead state at $M^{R}$ .

Reverse of the grammar

Or,

And the language of this grammar is: