*** Welcome to piglix ***

Greibach normal form


In formal language theory, 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. The normal form was established by Sheila Greibach and it bears her name.

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

or

where is a nonterminal symbol, is a terminal symbol, is a (possibly empty) sequence of nonterminal symbols not including the start symbol, is the start symbol, and ε is the empty word.


...
Wikipedia

...