Problem Solving in Automata, Languages, and Complexity

3.6 Pumping Lemmas for Context-Free Languages 147

/1*\

i “A’\

a* S C s

a* a*

(4 w

Figure 3.20: (a) A marked parse tree. (b) A leaf r outside the subtree
rooted at 4 cannot be marked.

Since L is infinite, the above construction is well defined for all stages
e > 0. From our assumption, we know that A is context-free, and so it is
accepted by a context-free grammar G. Let K > 0 be the constant associated
with grammar G, as given in Lemma 3.43. Now, choose a string w in A
with (WI > Ii’. Then, by Lemma 3.43, w can be decompsed as w = UVX~YX,
with 0 < IvyI 5 Iwxyl 5 I i’ and uvnxyn x E A for all n > 0. However, we
observe that lwl < I uv2xy2zl < lwl + Ii’ < 212~1, and so, by the property of
A, uv2xy2z $ A. This gives us% contradiction, and so shows that L must be
finite. cl

For regular
lemma, which

languages, we have established a

allows us to “pump” a specific

stronger form of the p umping
part of the string under con-
sideration. This stronger form often simplifies the proofs using the pumping
lemma. Can we also improve the pumping lemma for context-free languages
to a similar form? The answer is a qualified yes: We can only require that
the “pumping part” of the string must intersect with a predetermined specific
substring, but not completely contained in that substring.

• Lemma 3.51 (Ogden’s Lemma) Let G be a context-free grammar. Then
  there exists a constant K > 0, depending on G, such that if we mark at least
  K symbols of a string w in L(G), with Iwl > - K, then w can be decomposed
  as w = uvxyx satisfying the following conditions:
  (I) String v or string y has at least one marked symbol;
  (2) String vxy contains at most K marked symbols; and
  (3) uvnxynz E L(G) for all n > - 0.

Proof. The proof follows the same line of arguments of the proof of Lemma
3.43. We follow the definiton of d, m and K of Theorem 3.43. Suppose that T
is a parse tree of w, which has > - K marked symbols. We say an internal node
in T is a marked node if it has at least two children, both of which contain a
marked leaf as a descendant. For instance, Figure 3.20(a) shows a parse tree
with marked and unmarked nodes.