We can see the connection with programming languages clearly if we replace a
and b with left and right parentheses, respectively. The language L includes such
strings as (()) and () () () and is in fact the set of all properly nested parenthesis
structures for the common programming languages.
Here again there are many other equivalent grammars. But, in contrast to
Example 5.3, it is not so easy to see if there are any linear ones. We will have to
wait until Chapter 8 before we can answer this question.
Leftmost and Rightmost Derivations
In a grammar that is not linear, a derivation may involve sentential forms with
more than one variable. In such cases, we have a choice in the order in which
variables are replaced. Take, for example, the grammar G = ({A, B, S}, {a, b}, S,
P) with productions
This grammar generates the language L(G) = {a 2n b m : n ≥ 0, m ≥ 0}. Carry out a
few derivations to convince yourself of this.
Consider now the two derivations
and
In order to show which production is applied, we have numbered the productions
and written the appropriate number on the ⇒ symbol. From this we see that the