Greibach Normal Form 


Greibach Normal Form  (GNF):


It is another grammatical form of CFG where restrictions not on the length of the right sides of a production, but on positions in which terminal and variables can appear.


Production Form of GNF:


V → TV* or V → T | TV*







We use Greibach Normal Form (GNF) to convert Push Down Automata (PDA) though we can direct convert CFG to PDA.


Convert CFG to GNF then PDA by an algorithm



How to convert CFG to GNF:


Here we discuss one method to convert CFG to CNF is substitution method.


Let take a grammar for the conversion method. 




The above grammar is not followed GNF productions rules (V → TV*) because in this production 

(S → AB) we can see consecutive variables without a terminal.


Now we are converting given Context Free Grammar G to the corresponding GNF using substitution method:




In this case, we substitute A and B at this production S → aAB | bBB | bB by A → aA | bB | b and B → b.


So, G ≅ G1