Mathematical Foundation of Computer Science

DHARM

288 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

S

S

+

( )

SS

a ( S )

SSH

aa

Fig. 11.10

Hence, S ⇒N (a + (a H a)) is the yield of the derivation tree which is the concatenation of

all terminal symbols (leaves) of the tree from left-to-right.

Since, in the derivation sequence we derive the left most non terminal first. Hence, the

derivation is called ‘left-most-derivation (lm) and the derivation tree is left-most-derivation-

tree.

So, S ⇒N (a + (a H a))

lm
For right-most-derivation (rm) sequence derive right most non terminal first. Hence, we
get the right-most-derivation-tree.
Like in this example when we derive right most derivation first we go through a differ-
ent derivation sequence for the same terminal string ‘(a + (a H a))’ viz.
S ⇒ (S) [we start from this production because the first terminal string is ‘(’]
S ⇒ (S + S) [∴ S → S + S]
S ⇒ (S + (S)) [∴ S → (S)]
S ⇒ (S + (S H S)) [∴ S → S H S]
S ⇒ (S + (S H a)) [∴ S → a]
S ⇒ (S + (a H a)) [∴ S → a]
S ⇒ (a + (a H a)) [∴ S → a]

Hence, S ⇒N (a + (a H a))

rm

And its right most derivation tree is shown in Fig. 11.11

S

S

+

( )

SS

a ( S )

SSH

aa

Fig. 11.11