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.
Some do not permit the second form of rule and cannot transform context-free grammars that can generate the empty word.
[2] This conversion can be used to prove that every context-free language can be accepted by a real-time (non-deterministic) pushdown automaton, i.e., the automaton reads a letter from its input every step.