Once we see the argument intuitively, we are ready to proceed more
rigorously. Again we use induction. Assume that all w ∈ L with |w| ≤ 2n can be
derived with G. Take any w ∈ L of length 2n + 2. If w = aw 1 b, then w 1 is in L,
and |w 1 | = 2n. Therefore, by assumption,
Then
is possible, and w can be derived with G. Obviously, similar arguments can be
made if w = bw 1 a.
If w is not of this form, that is, if it starts and ends with the same symbol,
then the counting argument tells us that it must have the form w = w 1 w 2 , with w 1
and w 2 both in L and of length less than or equal to 2n. Hence again we see that
is possible.
Since the inductive assumption is clearly satisfied for n = 1, we have a basis,
and the claim is true for all n, completing our argument.
Normally, a given language has many grammars that generate it. Even
though these grammars are different, they are equivalent in some sense. We say
that two grammars G 1 and G 2 are equivalent if they generate the same language,
that is, if
As we will see later, it is not always easy to see if two grammars are
equivalent.
Example 1.14
Consider the grammar G 1 = ({A, S}, {a, b}, S, P 1 ), with P 1 consisting of the
productions