with n and m nonnegative, is an inherently ambiguous context-free language.
That L is context-free is easy to show. Notice that
where L 1 is generated by
and L 2 is given by an analogous grammar with start symbol S 2 and productions
Then L is generated by the combination of these two grammars with the
additional production
The grammar is ambiguous since the string a n b n c n has two distinct
derivations, one starting with
, the other with
. It does not, of
course, follow from this that L is inherently ambiguous as there might exist some
other unambiguous grammars for it. But in some way L 1 and L 2 have conflicting
requirements, the first putting a restriction on the number of a’s and b’s, while
the second does the same for b’s and c’s. A few tries will quickly convince you
of the impossibility of combining these requirements in a single set of rules that
cover the case n = m uniquely. A rigorous argument, though, is quite technical.
One proof can be found in Harrison 1978.
EXERCISES
1. Find an s-grammar for L (aaa*b + b).
2. Find an s-grammar for L = {a n b n : n ≥ 1}.