Greibach Normal Form Definition/Meaning:
A restricted type of context-free grammar, namely one in
which all productions have the form
A → bC1...Cn
i.e. each right-hand side consists of a terminal followed by (zero or more)
nonterminals. Any context-free language is generated by such a grammar, except
that derivation of the empty string, A, requires the additional production.
S → A
One significance of this form is that it makes clear the existence of an
equivalent pushdown automaton: on reading b the PDA can pop A from the stack
and push
C1 ... Cn
|
