where V is a finite set of terminal symbols, Σ (the alphabet)
is a finite set of terminal symbols, P is a set of rules,
and S is the start symbol.
A rule is written A->w where A E V and w E (V U ∑)*
A rule of the form A->λ is called a null or λ-rule
Properties of CFG are:
- These languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton.
- Context free languages are the theoretical basis for the syntax of most programming languages.
S->AbAbA
A->aA | λ
Generates the language of the grammar a*ba*ba*