Next: The Pumping Lemma: Examples
Up: Proving that a Language
Previous: Proving that a Language
  Contents
For any context-free grammar
, there is a number
, depending on
, such that
any string generated by
which has length greater than
can be written in
the form
, so that either
or
is non-empty, and
is
in the language generated by
for all
.
Proof:
Based on the above discussion, we can see that the number
is simply
.
James Power
2002-11-29