Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 291

I. lm derivation sequence

S ⇒ T + S ⇒ F + S ⇒ a + S ⇒ a + T ⇒ a + F H T ⇒ a + a H T

⇒ a + a H F ⇒ a + a H a

(Fig. 11.16 shows its lm derivation tree)

S

TS+

a FTH

a

F T

a

F

Fig. 11.16

II. rm derivation sequence

S ⇒ T + S ⇒ T + T ⇒ T + F H T ⇒ T + F H F ⇒ T + F H a

⇒ T + a H a ⇒ F + a H a ⇒ a + a H a

(Fig. 11.17 shows its rm derivation tree)

S

TS+

a FTH

a

F T

a

F

Fig. 11.17
After compare the derivation tree structures we find that both are similar. So the string
has a unique derivation tree hence G is an unambiguous grammar.

Example 11.13. Show that CFG G with productions
S → a | S a | b S S | S S b | S b S
is ambiguous.
Sol. If G is ambiguous then it must has two or more derivation trees for at least a strings of
L(G). Since L(G) = {a, aa, aaa, ......, baa, baaaa,....., aab,......, aba,......, baab,......}
l Test the ambiguity of G on string ‘baa’. For that following are the derivation se-
quences, i.e.,
n S ⇒ b S S ⇒ b a S ⇒ b a a (using lm derivation sequence)
n S ⇒ b S S ⇒ b S a ⇒ b a a (using rm derivation sequence)