What is a context-free grammar?

A context-free grammar $G=(V,\Sigma,S,P)$ is given by

• A finite set $V$ of variables or nonterminal symbols.

• A finite set $\Sigma$ of symbols or terminal symbols. We assume that the sets $V$ and $\Sigma$ are disjoint.

• A start symbol $S\in V$.

• A finite set $P \subseteq V\times (V\cup T)^*$ of productions. A production $(A,\alpha)$, where $A\in V$ and $\alpha\in(V\cup T)^*$ is a sequence of terminals and variables, is written as $A \to \alpha$.

As an example we define a grammar for the language of arithmetical expressions over $a$ (using only $+$ and $*$), i.e. elements of this language are $a+(a*a)$ or $(a+a)*(a+a)$. However words like $a++a$ or $)(a$ are not in the language.

We define $G=(\{E,T,F\},\{(,),a,+,*\},E,P)$ where $P$ is given by:

$$P = \{ E \to T$$

$$ E \to E + T$$

$$ T \to F$$

$$ T \to T * F$$

$$ F \to a$$

$$ F \to ( E ) \}$$

To save space we may combine all the rules with the same left hand side, i.e. we write

$$P = \{ E \to T \mid E + T$$

$$ T \to F \mid T * F$$

$$ F \to a \mid ( E )$$