186 ~ Theory of Computer Science
Solution
S ~ aAS ~ asbAS ~ aabAS ~ a
2 bbaS ~ a
2 b
2
a
2
(6.2)
Hence. S ~ a
2
b
2
a
2
. The derivation tree is given in Fig. 6.8.
s
a
a
Fig. 6.8 The derivation tree with yield aabbaa for Example 6.2.
Note: Consider G as given in Example 6.2. We have seen that S ~ a
2
b
2
a
2 ,
and (6.2) gives a derivation of a
2 b
2
a
2 .
Another derivation of a
2
b
2
a
2 is
S ~ aAS ~ aAa ~ aSbAa ~ aSbbaa ~ aabbaa
(6.3)
Yet another derivation of a
2
b
2
a
2 is
S ~ aAS ~ aSbAS ~ aSbAa ~ aabAa ~ aabbaa
(6.4)
In derivation (6.2), whenever we replace a variable X using a production,
there are no variables to the left of X. In derivation (6.3). there are no variables
to the light of X. But in (6.4), no such conditions are satisfied. These lead to
the following definitions.
DefInition 6.4 A derivation A ~ w is called a leftmost derivation if we
apply a production only to the leftmost variable at every step.
DefInition 6.5 A derivation A ~ w is a rightmost derivation if we apply
production to the rightmost variable at every step.
Relation (6.2). for example, is a leftmost derivation. Relation (6.3) is a
rightmost derivation. But (6.4) is neither leftmost nor rightmost. In the second
step of (6.4), the rightmost variable S is not replaced. So (6.4) is not a
rightmost derivation. In the fOUl1h step, the leftmost variable S is not replaced.
So (6.4) is not a leftmost derivation.
Theorem 6.2 If A ~ 11,' in G. then there is a leftmost derivation of w.