A Beginning Example

Let's give an example of a grammar for a language and then discuss the process of deriving strings from the productions. Let $A=\{a,b,c\}.$ Then a grammar for the language $A^{**}$ can be described by the following four productions:

$S$

$SaS$

$SbS$

$ScS$

How do we know that this grammar describes the language $A^{**}?$ We must be able to describe each string of the language in terms of the grammar rules. For example, let's see how we can use the productions $(3\mathrm{.}11)$ to show that the string aacb is in $A^{**}.$ We'll begin with the start symbol $S.$ Next we'll replace $S$ by the right side of production $SaS.$ We chose production $SaS$ because aacb matches the right$-$hand side of $SaS$ by letting $S=$acb. The process of replacing $S$ by $aS$ is called a derivation step, which we denote by writing

$S=>aS.$

A derivation is a sequence of derivation steps. The right$-$hand side of this derivation contains the symbol $S.$ So we again replace $S$ by $aS$ using the production $SaS$ a second time. This results in the derivation

$S=>aS=>$aaS

The right$-$hand side of this derivation contains $S.$ In this case we'll replace $S$