represents all possible derivations. Thus, G can derive only strings of the form
a n b n .
We also have to show that all strings of this form can be derived. This is
easy; we simply apply S → aSb as many times as needed, followed by S → λ.
Example 1.12
Find a grammar that generates
The idea behind the previous example can be extended to this case. All we need
to do is generate an extra b. This can be done with a production S → Ab, with
other productions chosen so that A can derive the language in the previous
example. Reasoning in this fashion, we get the grammar G =({S, A}, {a, b}, S,
P), with productions
Derive a few specific sentences to convince yourself that this works.
The previous examples are fairly easy ones, so rigorous arguments may seem
superfluous. But often it is not so easy to find a grammar for a language
described in an informal way or to give an intuitive characterization of the
language defined by a grammar. To show that a given language is indeed
generated by a certain grammar G, we must be able to show (a) that every w ∈ L
can be derived from S using G and (b) that every string so derived is in L.
Example 1.13
Take ∑ = {a, b}, and let n a (w) and n b (w) denote the number of a’s and b’s in
the string w, respectively. Then the grammar G with productions