values of m or xyz. On the other hand, the pumping lemma holds for every w ∈ L
and every i. Therefore, if the pumping lemma is violated even for one w or i,
then the language cannot be regular.
The correct argument can be visualized as a game we play against an
opponent. Our goal is to win the game by establishing a contradiction of the
pumping lemma, while the opponent tries to foil us. There are four moves in the
game.
1. The opponent picks m.
2. Given m, we pick a string w in L of length equal or greater than m. We are
free to choose any w, subject to w ∈ L and |w| ≥ m.
3. The opponent chooses the decomposition xyz, subject to |xy| ≤ m, |y| ≥ 1. We
have to assume that the opponent makes the choice that will make it hardest
for us to win the game.
4. We try to pick i in such a way that the pumped string w i , defined in Equation
(4.2), is not in L. If we can do so, we win the game.
A strategy that allows us to win whatever the opponent's choices is
tantamount to a proof that the language is not regular. In this, Step 2 is crucial.
While we cannot force the opponent to pick a particular decomposition of w, we
may be able to choose w so that the opponent is very restricted in Step 3, forcing
a choice of x, y, and z that allows us to produce a violation of the pumping
lemma on our next move.
Example 4.8
Show that
is not regular.
Whatever m the opponent pickson Step 1, we can always choose a w as
shown in Figure 4.5. Because of this choice, and the requirement that |xy| ≤ m,
the opponent is restricted in Step 3 to choosing a y that consists entirely of a’s. In
Step 4, we use i = 0. The string obtained in this fashion has fewer a’s on the left
than on the right and so cannot be of the form ww R . Therefore, L is not regular.
Figure 4.5