Definition: A context-free
grammar (CFG) is a quadruple G = (N, T, P, S),
where
• N is an alphabet of nonterminals
• T is an alphabet of terminals, N Ç T = Æ
• P is a finite set of rules
of the form A ® x,
where A Î N, x Î (N È T)*
• S Î N is the start nonterminal
• Strictly mathematically, P is a
relation from N to (N È T)*
• Instead of (A, x) Î P, we write A ® x
Î P