118 CONTEXT-FREE LANGUAGES
Finally, we observe that if z is generated by X from the derivation (3.1),
then au must be the longest prefix of z having property PI, since c(u) = 0
implies c(aub) = 0 and, for every prefix w of U, c(w) > 0 implies c(aw) > 1.
Thus, the matching of the first a in x with the symbol bright after u is unique.
It follows from an induction argument that the parsing of x: in Gx is unique.
Next, we define a grammar Gy :
By a symmetric argument, we know that GY is an unambiguous grammar for
set B.
We are now ready to define the unambiguous context-free grammar G3 for
L:
S + uXbS 1 bYuS 1 E, X + uXbX 1 E, Y .+ bYuY 1 E.
It is obvious that L(G3) C L. C onversely, we prove, by induction on the
length of z:, that if z E L then 2 has a unique parse tree in G3. This is trivial
for x = E. For the inductive step, let x E {a, b}+ be a string that begins with
a. Then, we can write x = uubw, where au is the longest prefix of x satisfying
property PI. By the same argument above, there is a unique way to parse
X 3 u. Furthermore, we have c(u) = 0 and so C(V) = 0. By induction, we
also have a unique way to parse S % w. Thus, there is a derivation of x:
S 3 uXbS % uubS 3 uubv = x.Furthermore, we argue that this is the unique parsing of x; that is, in the first
step of a derivation S 3 uXbS $ x, the first symbol a must be matched
with the symbol b after u.
First, we show that a cannot be matched with any b in u: If u = ulbuz for
some ur, ~2, then we must have c(u1) > 0, since, by property PI, c(uulb) > 0.
Thus, ur cannot be derived from X. Second, we argue that a cannot be
matched with any b in K If 21 = qbv2, then c(ub) = c(uub) - 1 = -1 and,
hence, ubq has a prefix with a negative value of c. Thus, ubwl 4 A and so X
cannot generate it.
The same argument works for strings x beginning with b. This concludes
our proof that Gs is an unambiguous grammar for L. Cl
The above examples showed that some ambiguous context-free grammars
can be modified into an unambiguous one. This is, however, not always possi-
ble. A context-free language is called inherently ambiguous if every grammar
generating it is ambiguous. A typical example of an inherently ambiguous
context-free language is L = { dbjc” 1 i = j or j = k}. Intuitively, for any
context-free grammar G that generates L, there must be a method to generate
strings of the form uibick, and a separate method to generate strings of the
form-u’ bk ck. Then, for strings of the form uibici, there would be two differ-
ent ways to generate it. The formal proof of this fact requires more careful