Greibach Normal Form (GNF)
Definition: Let G = (N, T, P, S) be a CFG.
G is in Greibach normal form if every rule in P is of this form
• A ® ax, where A Î N, a Î T, x Î N*
Example:
G = (N, T, P, S), where N = {B, S}, T = {a, b},
P = {S ® aSB, S ® aB, B ® b}
is in Greibach normal form.
Note: L(G)  = {anbn: n ³ 1}
3/31