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: Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a nonterminal symbol and w is a string consisting of terminals and/or non-terminals. ...

or

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. A nonterminal symbol is that symbol which has the capability of being further defined in terms of terminals and/or non-terminals. ... A terminal symbol, in BNF jargon, is a symbol that represents a constant value. ...

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. The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data. ...

Given a grammar in GNF and a derivable string in the grammar with length n, any top-down parser will halt at depth n. This article or section does not cite its references or sources. ...

Greibach normal form is named after Sheila Greibach. Sheila Greibach (1939-) is a researcher in formal languages, automata, compiler theory in particular; and computer science in general. ...

See also

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

The Backus-Naur form (BNF) (also known as Backus normal form) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. ... In computer science, a formal grammar is in Chomsky normal form iff all production rules are of the form: A → BC or A → α or S → ε where A, B and C are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and... A formal grammar is in Kuroda normal form iff all production rules are of the form: AB → CD or A → BC or A → B or A → α where A, B, C and D are nonterminal symbols and α is a terminal symbol. ...

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.)