Greibach

Greibach refers to Sheila Greibach, a computer scientist known for her contributions to formal language theory. The most widely cited concept bearing her name is Greibach normal form, a canonical form for context-free grammars.

Greibach normal form (GNF) requires that every production in a grammar is of the form A → a α, where a is a terminal symbol and α is a (possibly empty) string of nonterminal symbols. The start symbol S may derive epsilon if epsilon is in the language. In GNF, each rule begins with a terminal, which supports straightforward leftmost derivations and has implications for parsing strategies.

A central result is that every context-free language has an equivalent grammar in Greibach normal form. The transformation is constructive, enabling theoretical analyses and certain parsing techniques. However, converting to GNF can significantly increase the size of the grammar, with worst-case growth that can be exponential.

Greibach normal form is one of several standard forms for context-free grammars and intersects with topics in automata theory, such as pushdown automata, and with comparisons to other forms like Chomsky normal form. The form is primarily used in theoretical investigations of the structure of context-free languages and in the study of derivations and parsing algorithms.