Revision 53928 of "Greibach_normal_form" on enwiki

To say that a [[context-free grammar]] is in '''Greibach normal form''' (GNF) means that all production rules are of the form:
:<math>A \to \alpha X</math>
where ''A'' is a [[nonterminal symbol]], &alpha; 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]].

==See also==
*[[Chomsky normal form]]
*[[Kuroda normal form]]

[[de:Greibach-Normalform]]
[[Category:Formal languages]]