Greibach normal form

A context-free grammar is in Greibach normal form (GNF) iff all production rules are of the form:

A -> αX

where A is a nonterminal symbol, α is a terminal symbol and X is (possibly empty) sequence of nonterminal symbols.

No grammar in GNF can generate the null string. Conversely, every context-free grammar which does not generate the null string can be transformed into an equivalent grammar in Greibach normal form. This can be used to prove that every context-free language can be accepted by a non-deterministic pushdown automaton.

Greibach normal form is named for Sheila Greibach (1939-), who is currently Professor of Computer Science at the University of California, Los Angeles.