The language of a grammar

How do we check whether a word $w\in\Sigma^*$ is in the language of the grammar? We start with the start symbol $E$ and use one production $V\to\alpha$ to replace the nonterminal symbol by the $\alpha$ until we have no nonterminal symbols left - this is called a derivation. I.e. in the example $G$:

$$E \Rightarrow _{G} E + T$$

$$ \Rightarrow _{G} T + T$$

$$ \Rightarrow _{G} F + T$$

$$ \Rightarrow _{G} a + T$$

$$ \Rightarrow _{G} a + F$$

$$ \Rightarrow _{G} a + (E)$$

$$ \Rightarrow _{G} a + (T)$$

$$ \Rightarrow _{G} a + (T*F)$$

$$ \Rightarrow _{G} a + (F*F)$$

$$ \Rightarrow _{G} a + (a*F)$$

$$ \Rightarrow _{G} a + (a*a)$$

Note that $\Rightarrow _G$ here stands for the relation derives in one step and has nothing to do with implication. In the example we have always replaced the leftmost non-terminal symbol (hence it is called a leftmost derivation) but this is not necessary.

Given any grammar $G=(V,\Sigma,S,P)$ we define the relation derives in one step

$$\Rightarrow _G \subseteq (V\cup T)^*\times (V\cup T)^*$$

$$\alpha V\gamma \Rightarrow _G \alpha\beta\gamma :\iff V \to \beta \in P$$

The relation derives is defined as²

$$\Rightarrow ^*_G \subseteq (V\cup T)^*\times (V\cup T)^*$$

$$\alpha_0 \Rightarrow ^*_G \alpha_n :\iff \alpha \Rightarrow _G \alpha_1 \Rightarrow _G \dots \alpha_{n-1} \Rightarrow _G \alpha_n$$

this includes the case $\alpha\Rightarrow _G^*\alpha$ because $n$ can be 0.

We now say that the language of a grammar $L(G)\subseteq \Sigma^*$ is given by all words (over $\Sigma$) which can be derived in any number of steps, i.e.

$$L(G) = \{ w\in\Sigma^* \mid S \Rightarrow ^*_G w \}$$

A language which can be given by a context-free grammar is called a context-free language (CFL).