Note that if we had chosen a w too short, then the opponent could have
chosen a y with an even number of b’s. In that case, we could not have reached a
violation of the pumping lemma on the last step. We would also fail if we were
to choose a string consisting of all a’s, say,
which is in L. To defeat us, the opponent need only pick
Now w i is in L for all i, and we lose.
To apply the pumping lemma we cannot assume that the opponent will make
a wrong move. If, in the case where we pick w = a 2m , the opponent were to pick
then w 0 is a string of odd length and therefore not in L. But any argument that
assumes that the opponent is so accommodating is automatically incorrect.
Example 4.9
Let Σ = {a, b}. The language
is not regular.
Suppose we are given m. Since we have complete freedom in choosing w, we
pick w = a m b m+1 . Now, because |xy| cannot be greater than m, the opponent
cannot do anything but pick a y with all a’s, that is
We now pump up, using i = 2. The resulting string
chosen a y with an even number of b’s. In that case, we could not have reached a
violation of the pumping lemma on the last step. We would also fail if we were
to choose a string consisting of all a’s, say,
which is in L. To defeat us, the opponent need only pick
Now w i is in L for all i, and we lose.
To apply the pumping lemma we cannot assume that the opponent will make
a wrong move. If, in the case where we pick w = a 2m , the opponent were to pick
then w 0 is a string of odd length and therefore not in L. But any argument that
assumes that the opponent is so accommodating is automatically incorrect.
Example 4.9
Let Σ = {a, b}. The language
is not regular.
Suppose we are given m. Since we have complete freedom in choosing w, we
pick w = a m b m+1 . Now, because |xy| cannot be greater than m, the opponent
cannot do anything but pick a y with all a’s, that is
We now pump up, using i = 2. The resulting string