Index
Computer Science
Formal Language and Automata
Greibach Normal Form

Greibach Normal Form

A context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language.


More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form:

$A \to a A_1 A_2 \cdots A_n$

or

$S \to \varepsilon$

where $A$ is a nonterminal symbol, $a$ is a terminal symbol, $A_1 A_2 \ldots A_n$ is a (possibly empty) sequence of nonterminal symbols not including the start symbol, $S$ is the start symbol, and ε is the empty word.

http://www.iitg.ac.in/gkd/ma513/oct/oct18/note.pdf