Greibach Normal Form

languages

Definition

Greibach Normal Form

A context-free grammar is in Greibach normal form if every production rule has the form

$$A\to aw$$

where $a\in T$ is a terminal symbol, $A\in N$ is a non-terminal symbol, and $w\in N^{\ast }$ is a (possibly empty) string of non-terminal symbols.

For every context-free grammar $G$, one can construct an equivalent grammar in Greibach normal form.