Greibach normal form

In computer science, to say that a context-free grammar is in Greibach normal form (GNF) means that all production rules are of the form:

$A\to \alpha X$

or

$S\to \lambda$

where A is a nonterminal symbol, α is a terminal symbol, X is a (possibly empty) sequence of nonterminal symbols not including the start symbol, S is the start symbol, and λ is the null string.

Observe that the grammar must be without left recursions.

Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. (Some definitions do not consider the second form of rule to be permitted, in which case a context-free grammar that can generate the null string cannot be so transformed.) This can be used to prove that every context-free language can be accepted by a non-deterministic pushdown automaton.

Given a grammar in GNF and a derivable string in the grammar with length n, any top-down parser will halt at depth n.

Greibach normal form is named after Sheila Greibach.

See also

• Backus-Naur form
• Chomsky normal form
• Kuroda normal form

References

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X. (See chapter 4.)