Mathematical Foundation of Computer Science

DHARM

292 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Both shows unique derivation tree. Hence G may be unambiguous.

l Test with the string ‘baaab’.

We construct most possible derivation sequences for this string, i.e.,

n S ⇒ S S b ⇒ b S S S b ⇒ b a S S b ⇒ b a a S b ⇒ b a a a b

(using lm derivation sequences).

n S ⇒ b S S ⇒ b a S ⇒ b a S S b ⇒ b a a S b ⇒ b a a a b

(using lm derivation sequences).

n S ⇒ b S S ⇒ b S S S b ⇒ b S S a b ⇒ b S a a b ⇒ b a a a b

(using rm derivation sequences)

There derivation trees are shown in Fig. 11.18(a) (b) (c) respectively.

S

S S b

b S S a

a a

S

b S S

a SS b

a a

S

b S S

a SS b

a a

lm derivation tree 1 lm derivation tree 2 rm derivation tree Similar to

lm derivation tree 2

(a)(b)(c)

Fig. 11.18
Thus, for this string we have two different derivation trees that are shown above. So,
grammar G fails to provide unique derivation tree, hence G is an ambiguous CFG.
Example 11.14. Show that CFG G with productions
S ⇒ S(S) | ∈
is unambiguous.
Sol. Construct the context free language (CFL) i.e., (G) = {∈, ∈(∈), ∈(∈)(∈), ∈(∈(∈)),......}
Now test the ambiguity of CFG G and show that there is a unique derivation tree for all
of its strings ∈ L(G).
l For string ∈ there is one and only one possible derivation sequence S ⇒ ε.
l For string ∈(∈):
S ⇒ S(S) ⇒∈(S) ⇒∈(∈)
We get a unique derivation tree either derive lm or rm derivation sequence.
l For string ∈(∈) (∈):
S ⇒ S(S) ⇒ S(S)(S) ⇒∈(S)(S) ⇒∈(∈)(S) ⇒∈(∈)(∈)
There is no other derivation sequence possible for this string. Hence, we again reach
to unique derivation tree.