# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# 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$

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.