Grammar question assignment-42759

  1. The given grammar is,



a)      There are following  productions in the given grammar.


The derived grammar (G’) from the given grammar by removing the  production is,



b)      In the grammar G’, there are following unit productions,


After removal of the unit production the new equivalent grammar (G’’) will be,


c)       The grammar G’’ is,



To derive the equivalent grammar in CNF, some new non-terminals, P1, P2 and P3 will be added. The new form will be,












  1. The given grammar G in CNF is has the following rules,





The given string to check the membership, is,




  1. The DPDA with all transitions is,

The language is,


The new language will be,  . To make the DPDA accepting the new language, we need accept strings with any number of a’s (including null string) and strings of L.

The modified DPDA will be,

Cant solve it, as the question is technically wrong. In language L, it is given as . So, the alphabet has symbols a and b only. But in the graphical representation of the DPDA corresponding to L, symbol c has been used, that is beyond the alphabet set.