Equivalent grammar

58 Views Asked by At

Consider the grammar $G=(\{S,A,B\},\{0,1\},P,S)$, where $P$ consists:

$S\to AB$

$A\to BSB$

$A\to BB$

$B\to 0A1$

$B\to 0$

$A\to 1$

$B\to e$

Find equivalent grammar for which S does not appear on the right of any productions and $S\to e$ is the only production with e on the right.

This is a problem from Formal languages and their relation to automata, 4.16.

I tried to figure out what is L(G), but it was complicated. Then, I made grammar $G'=(\{S,A,B,C\},\{0,1\},P',S)$, where $P'$:

$S\to AB$

$A\to BCB$

$C\to AB$

$A\to BB$

$B\to 0A1$

$B\to 0$

$A\to 1$

but problem is to convert $B\to e$ in corresponding form.