The formal definition of a context-free grammar (CFG) is a 4-tuple (V, Σ, R, S), where
- V is a finite set of variables
- Σ is a finite set of terminals
- R is a finite set of rules of the form {A → s | A ∈ V, s ∈ (V ∪ Σ)*}
(variable → string of variables and terminals)
- S ∈ V is the start variable
Let u, v and w be elements of (V ∪ Σ)* (strings of variables and terminals). If A → w is a rule of the grammar (A ∈ R), then uAv yields uwv. This is generally written uAv ⇒ uwv. Furthermore, one can write u ⇒* v if u = v or there is a sequence u1, u2,…,uk such that k ≥ 0 and u1 ⇒ u2 ⇒…⇒ uk ⇒ v. One says that v is derivable from u.
The language of a grammar is {w ∈ Σ* | S ⇒* w}
Introduction to the Theory of Computation (ISBN 0-534-94728-X) was consulted in the creation of this writeup.