gate 2005

Question

Consider the following CFG, find the number of productions in the minimized grammar after it was convert it into Greibach normal form.
S → AA| 0, A → SS | 1

 

plzzz explain how to convert the given grammer into gnf in detail.

Answer 1

The grammar is already in CNF so need of conversion.

GNF IS LOOKS LIKE

or

  

S->1A | SSA| 0

A->0S |AAS | 1.

it is left recursive so eliminate left recursion 

S->0S' |1AS'

S'->SAA' | $\epsilon$             // substitute 's' by previous productions.

S'->0S'AA' | 1AS'SAA'             

A->0SA' |1A'

A'->ASA' | $\epsilon$

A'->0SA'SA' | 1A'SA'.

SO FINAL GNF IS

S->0S' |1AS'

S'->0S'AA' | 1AS'SAA'   |$\epsilon$

A->0SA' |1A'

A'->0SA'SA' | 1A'SA'. |$\epsilon$

 

Comments

$S'->SAS'$ instead of $S'->SAA'$