context-free grammar (idea)

The formal definition of a context-free grammar (CFG) is a 4-tuple (V, Σ, R, S), where

1. V is a finite set of variables
2. Σ is a finite set of terminals
3. R is a finite set of rules of the form {A → s | A ∈ V, s ∈ (V ∪ Σ)*}
   (variable → string of variables and terminals)
4. 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 u₁, u₂,…,u_k such that k ≥ 0 and u₁ ⇒ u₂ ⇒…⇒ u_k ⇒ 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.