Problem Solving in Automata, Languages, and Complexity

116 CONTEXT-FREE LANGUAGES

E

/I\

E -I- T

/I\ I

E

I

T

I I I

F F a

I I

a b

E - T

/I\

* F

/I‘\

F F c E >

I I

b

/I\

a Et-T

I I

T F

I I

F b

(4 (b)

Figure 3.9: (a) Th e unique parse tree for a - b si: a + b. (b) The unique parse
tree for a -b*(a$b).

For Grammar Gz, it comes from the occurrences of AA or BB in the
sentential forms. Recall that A generates the set of all strings w with Sita =
#b(w) + 1. Now, suppose w = z:z, with #a(x) = #b(z) + 1, #~(~) = #b(Y)
and #&z) = #b(z) + I. Th en, we have two ways to generate w from AA.
One way is to use A > arty and A > x. The other way is to use A 3 ;I:
and A 3 yx. Based on this idea, we can construct two leftmost derivations
for the string bbclbbuaa:

S + bA =+ bbAA 3 bbaSA =+ bbubAA =+ bb~bbAAA 3 bbubba~~,

S 3 bA =P bbAA * bb~SA 3 bbaA =+ bbubAA ---*, bb~bbAAA

$ bbabbaaa.

(b) We show how to modify grammar G1 into an unambiguous grammar,
and leave the modification of Gz into an unambiguous grammar as an exercise
(Exercise 5).
We observe that if x E L, then a parse of ;t: must match each occurrence
of a in cx: with a unique b in L If there are more than one way to match
an occurrence of a with some b then we have ambiguity. To eliminate this
ambiguity, we read string x: from left to right and try to match the most
recently read unmatched occurrences of a and b. For instance, suppose x =
ubuubb~ then the matching must be done as this:

I 1

abaabb

u u

and the matching