Chapter 6: Context-Free Languages ~ 187
Proof We prove the result for every A in v'v by induction on the number
of steps in A :b 'i'. A ::::} W is a leftmost derivation as the L.H.S. has only
one variable. So there is basis for induction. Let us assume the result for
derivations in atmost k steps. Let A n~ w. The derivation can be split as
A ::::} X j X 2 ... XII! db w.
The string W can be split as \1'IW2 ... w'" such that Xi ::::} Wi (see the
Remark appended before Example 6.2). As Xi :b Wi involves atmost k steps
by induction hypothesis, we can find a leftmost derivation of Wi' Using these
leftmost derivations. we get a leftmost derivation of W given by
A ::::} X j X 2 ... XII! :b w j X 2 ... x",:b WjW2X3 ... X", ... :b w!,'i'2
Will
Hence by induction the result is true for all derivations A :b w.
Corollary Every derivation tree of W induces a leftmost derivation of w.
Once we get some derivation of \1'. it is easy to get a leftmost derivation of
W in the following way: From the derivation tree for w, at every level consider
the productions for the variables at that level, taken in the left-to-right ordering.
The leftmost derivation is obtained by applying the productions in this order.
EXAMPLE 6.3
Let G be the grammar 5 ~ OB 11A. A ~ 0 I05 11AA, B ~ 1115 IOBB. For
the string 00110101, find (a) the leftmost derivation, (b) the rightmost
derivation, and (c) the derivation tree.
Solution
(a) 5::::} OB ::::} OOBB ::::} 001B ::::} 00115
::::} 021 2 0B ::::} 0 2 1 2 015 ::::} 021 2 0lOB ::::} 02}20101
(b) 5::::} OB ::::} OOBB ::::} 00B15 ::::} OOBlOB
::::} 02B1015 ::::} 02BlOlOB ::::} 02BlO101 ::::} 0 2 110101.
(c) The derivation tree is given in Fig. 6.9.
s
B
s
o
Fig. 6.9 The derivation tree with yield 00110101 for Example 6.3.
o