FOR FREE YEAR SOLVED

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 $\mathbf{\left(}{\mathbf{G}}^{\mathbf{R}}\mathbf{\right)}$ = reverse of language ${\mathbf{L}}^{\mathbf{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 $\mathbf{\left(}{\mathbf{M}}^{\mathbf{R}}\mathbf{\right)}$ of the machine M.

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

Now, this ${\mathbf{G}}^{\mathbf{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 ${\mathbf{M}}^{\mathbf{R}}$.

Reverse of the grammar 

Or,

And the language of this grammar is: