3.6 Pumping Lemmas for Context-Free Languages 149
Example 3.53 Show that L = {bi,#bi,# l. .#bik 1 k > 2, each bij is the
binary representation of integer ij > 0, and (il, i2,... , i&contains an integer
occurring exactly twice} is not context-free.
Proof. Proving this directly using the pumping lemma would be tedious. By
the closure property of Example 3 .39, we can restrict our attention to the set
Ll = L n 10*#10*#10*
= {lOi#lOj#lOk 1 i = j # k or i = k # j or j = k # i}.Now, by a proof similar to that of
not context-free and it follows that L
Example 3.52, we can prove that L1 is
is not context-free.^0The following result was promised in Section 3.3, and is an interesting
application of Ogden’s lemma.
- Example 3.54 Show that the language L = {aWck 1 i = j or j = k} is
inherently ambiguous.
Proof. Suppose, to the contrary, that G is an unambiguous context-free gram-
mar for L. Let K be the constant associated with G, as given in Ogden’s
lemma. Now, consider a string w = ambmcm+m! in L, where m > K and
m! > 2772. We mark all occurrences of letter a. By Ogden’s lemma, we can
write zu as w = uv~yx satisfying conditions (l)-(3) of Ogden’s lemma. In
fact, by the proof of Ogden’s lemma, we can say more about the derivation of
w. That is, there must be a nonterminal A such that
S 2 uAx 3 uvAyz 3 uvxyx.That is, A 3 vAy and A 3 x.
Let us study the string a = uv2xy2x in L. Recall that #a(a) denotes
the number of occurrences of symbol a in a string a. First, as argued in
the proof of Example 3.52, each of v and y can hold at most one type of
symbols in {a, b, c}, for otherwise a is no longer of the form ui bjck. Next,
we observe that v and y can have at most m occurrences of symbol b and
so #b(a) < 2m < m + m! < #&). It follows that #&) = #b(a). By
condition (1,, we know that #a (a) > m.. It follows from the above discussion
that v = ui and y = bi for some i, 1 < - i < - m.
Now, let n = m!/i + 1, and we get a derivation of the string
P = uvnxynz = a m+(n-l)ibm+(n-l)icm+m!
= am~m!b?'n+m!cm+m!S 3 uAz 3 uvAyx 3 uvnAynz 3 uvnxynz = p. (3 2).
Next, we consider the string w’ = um+m’ bmcm. Applying Ogden’s lemma
to w’, with all letters c marked, we get w’ = ulvlxlylzl such that for some
nonterminal B,
S 3 ulBxl 3 ulvlBylxl 3 ulvlxlylxl.