Greibach Normal Form

Question

Convert the following grammar into Greibach Normal Form.

E-> E + T | T
T-> T*F | F
F->(E) | a

 

I am unable to process this type of grammer into GNF, Can someone please provide a detailed explaination?

Answer 1

In Greibach Normal Form, all production rules are of the form: 

Converting the above grammar to GNF, we shall get the following:

$F \rightarrow a$
$F \rightarrow (EP$
$P \rightarrow\; )$

$T \rightarrow a$
$T \rightarrow (EP$
$T \rightarrow a F_1$
$T \rightarrow (EPF_1$
$F_1 \rightarrow *F$

$E \rightarrow a$
$E \rightarrow (EP$
$E \rightarrow a F_1$
$E \rightarrow (EPF_1$
$E \rightarrow aE_1$
$E \rightarrow (EPE_1$
$E \rightarrow a F_1E_1$
$E \rightarrow (EPF_1E_1$
$E_1 \rightarrow +T$