lengths of the strings v, x, and y depend only on the productions of the grammar
and can be bounded independently of w so that (8.2) holds. Finally, since there
are no unit-productions and no λ-productions, v and y cannot both be empty
strings, giving (8.3).
Figure 8.1
This completes the argument that (8.1) to (8.4) hold.
This pumping lemma is useful in showing that a language does not belong to
the family of context-free languages. Its application is typical of pumping
lemmas in general; they are used negatively to show that a given language does
not belong to some family. As in Theorem 4.8, the correct argument can be
visualized as a game against an intelligent opponent. But now the rules make it a
little more difficult for us. For regular languages, the substring xy whose length
is bounded by m starts at the left end of w. Therefore, the substring y that can be
pumped is within m symbols of the beginning of w. For context-free languages,
we only have a bound on |vxy|. The substring u that precedes vxy can be
and can be bounded independently of w so that (8.2) holds. Finally, since there
are no unit-productions and no λ-productions, v and y cannot both be empty
strings, giving (8.3).
Figure 8.1
This completes the argument that (8.1) to (8.4) hold.
This pumping lemma is useful in showing that a language does not belong to
the family of context-free languages. Its application is typical of pumping
lemmas in general; they are used negatively to show that a given language does
not belong to some family. As in Theorem 4.8, the correct argument can be
visualized as a game against an intelligent opponent. But now the rules make it a
little more difficult for us. For regular languages, the substring xy whose length
is bounded by m starts at the left end of w. Therefore, the substring y that can be
pumped is within m symbols of the beginning of w. For context-free languages,
we only have a bound on |vxy|. The substring u that precedes vxy can be