Context-Free Grammar: Definition
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
• A ® x means that A can be replaced with x
• A ® e is called e-rule
Mathematical Note on Rules:
3/50