Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 289

Thus, we may find more derivation sequences and consequently more derivation trees
for a single terminal string.
Every tree has exactly one left derivation sequence and exactly one right derivation
sequence and also possible that both derivation sequences may be the same. Hence, a string
may have more than one derivation trees.

Example 11.11. Fig. 11.12 shows a left-most-derivation tree for the string ‘a + a H a’ using the
previous grammar G, i.e. {S, {+, , (, ), a}, S, {S → S + S/S S/(S)/a}.

S

SS+

a SSH

aa

Fig. 11.12

For the following derivation sequence:

S ⇒ S + S ⇒ a + S ⇒ a + S ⇒ S ⇒ a + a H S ⇒ a + a H a

There exists another lm derivation sequence for the same string, i.e.,

S ⇒ S H S ⇒ S + S H S ⇒ a + S H S ⇒ a + a H S ⇒ a + a H a

So, there exists another lm derivation tree shown in Fig. 11.13.

S

S +

a

SSH

S a

a

Fig. 11.13

Next, we see the right-most-derivation sequences for the same string, i.e.,

S ⇒ S H S ⇒ S ∗ a ⇒ S + S H a ⇒ S + a H a ⇒ a + a H a

or S ⇒N a + a H a

rm

Fig. 11.14 shows its rm derivation tree.

S

S +

a

SSH

S a

a

Fig. 11.14