Definition

Explaining
the Game

Starting the Game

User
Goes First

Computer Goes First

This game approach to the pumping lemma is based on the approach
in Peter Linz's *An Introduction to Formal Languages and Automata.*

JFLAP defines a regular pumping lemma to be the following. Let *L*
be an infinite regular language. Then there exists some positive
integer *m* such that any *w* that is a member of
*L* with |*w*| ≥ *m* can
be decomposed as

*w* = *xyz*,

with

|*xy*| ≤ *m*,

and

|*y*| ≥ 1,

such that

*w _{i}* =

is also in *L* for all *i* = 0, 1, 2, ....

In other words, any sufficiently long string in *L* can be
broken down into three parts such that any number of repetitions of
the middle part (pumping the middle part) will still yield in a
string in *L*.

JFLAP treats the regular pumping lemma as a two-player game. In
the game below, Player A is trying to find a *xyz* decomposition
that is always in the language no matter what the *i* value is.
Player B is trying to make it as hard as possible for player A to do
so. If player B can pick a strategy such that he or she will always
win regardless of player A's choices, meaning that no adequate
decomposition exists, it is equivalent to proof that the language is
not regular. The game is played like this:

Player A picks an integer for

*m*.Player B picks a string

*w*such that*w*is a member of*L*and |*w*| ≥*m*.Player A picks the partition of

*w*into*xyz*such that |*xy*| ≤*m*and |*y*| ≥ 1.Player B picks an integer

*i*such that*xy*is not a member of^{i}z*L*. If player B can do so player B wins, otherwise, player A wins.

There are two possible modes for the game, when the user goes first and when the computer goes first. In the first mode, the user is player A and the computer is player B, and thus the user should be trying to find an acceptable decomposition to pump. In the second mode, the user is player B and the computer is player A, and thus the user should be trying to prevent the computer from generating a valid decomposition.

To start a regular pumping lemma game, select **Regular Pumping
Lemma** from the main menu:

You will then see a new window that prompts you both for which mode you wish to utilize and which language you wish to work on. The default mode is for the user to go first. A list of languages is also shown, some of which are regular and some of which are not regular. To proceed to a language, click on the appropriate “Select” button, and a new screen will come up based on the language chosen and the mode selected when the button was pushed.

Let's do an example for when the user goes first. Since the “You
go first” option is already selected, we do not need to do anything
in the top panel. Now we need to choose a language. Let's try the
first language on the screen, L = {a^{n}b^{n} : n ≥
0}. Go ahead and press the “Select” button to the right of the
language. The following screen should come up.

You may be curious about all the various items on the screen. We
will touch all of them in time, but for now, let's play the game. We
see that our objective in this mode is to find a valid partition, and
that the first step that we need to preform is to choose a value for
*m*. Go ahead and enter a fairly large value for *m*, such
as 20, in the box where you are prompted. If the value is too large,
the following message should appear in the panel where you entered *m*.

JFLAP will only accept values for *m* in a finite range, both
so *m* is large enough and so unnecessarily large values are
avoided. Now, go ahead and enter “4”, which is a value of m in
accepted range. The error message should disappear, and the following
two panels should now be visible on the screen under the *m*
panel.

The computer has chosen a value for *w*, and now the game
prompts you to decompose the string. You can adjust the *x*, *y*,
and *z *substrings by using the sliders to set the boundaries
between them. The first slider will set the boundary between *x*
and *y*, and the second will set the boundary between *y *and
*z*. If the decomposition is acceptable, the “Set xyz”
button will become visible and the message at the bottom of the panel
will inform you that you can set the button. If it is unacceptable,
the message at the bottom will inform you what the problem is with
the current decomposition.

Let's have *x* and *y* both
equal “aa”. Go ahead and slide the top slider over two spaces.
You should notice that the bottom slider also moves too. Then, slide
the bottom slider over two more spaces, and then click the visible
“Set xyz” button. You should notice that the decomposition for
each substring appears in the appropriate boxes as you move the
sliders, in addition to the lengths of the substrings (note however
that all fields may not be filled in if the decomposition is
invalid). When finished, the message in the decomposition panel will
disappear, the last two panels will become visible, and the whole
screen will look like this.

There are a number of things that you should notice. First, in the
panel below the decomposition panel, we see that the computer has
chosen a value for *i*, which is 0. It also shows the pumped
string, which is “aabbbb”. The panel below informs you that you
have lost, as the pumped string is not in the language. This panel
also allows you to see an animation of how the pumped string is
assembled. Press the “Step” button to see each step in the
animation, and the button will lose its visibility when all steps
have been completed. “Restart”, if visible, will restart the
animation at the beginning. When the animation is finished, the
bottom panel should look like this.

You should also notice that there is new information in the text
box in the top panel. What is listed here is all the attempts that
you have made to win this game. Scroll down a little in this text box
and you should see your decomposition, *i* value, and result
(either *Failed *or *Won*) for each attempt.

Since we have made only one attempt so far, only one attempt is
listed. If we try a few more times, more attempts will be added to
the list. The more recent the attempt, the closer it will be to the
top of the list. There are a variety of ways to try again. If we are
happy with our *m* and *w* values, we can simply choose a
new decomposition in the decomposition panel and press the “Set
xyz” button. If, however, we wish to change the *m* value, we
can either enter a new value in the *m* panel directly or press
the “Clear All” button, which is in the top panel, and then enter
a new *m* value. If you press the “Clear All” button, notice
that the list of attempts remains visible. After entering a new *m*
value and after the computer picks a new *w* value, you would
then choose a new decomposition. The visibility of all panels will be
updated to reflect the current stage of the game.

After a few attempts, you may notice that you never win, no matter
what *m *value you choose or which decomposition you pick.
However, if you don't spot the strategy that the computer is
employing, you may wonder whether you are simply choosing your values
poorly or whether it is indeed impossible to win. Once you have made
enough attempts, feel free to press the “Explain” button in the
top panel. You will now see, in the text box where the attempts are
listed (you can still see them if you scroll down further), whether a
valid partition exists. Below this information is an informal,
intuitive proof about why there is or is not a valid partition. For
this example, there is indeed no valid partition. To get rid of the
proof and information about the possibility of a valid partition,
simply click on the “Clear All” button.

The example you just generated is available in regUserFirst.jff.

When finished, dismiss the tab, and you will return to the
language selection screen. In the top panel, click on “Computer
goes first.” Then, choose the first language, L = {a^{n}b^{n}.
: n ≥ 0}, again. The following screen should come up.

You will notice a few things different
from when you went first. First, the objective has changed. Your
purpose is to prevent the computer from finding a valid partition.
Second, the messages for each step in the game have changed,
reflecting the different tasks you must perform as player B. The
computer has chosen a value for *m* within the permissible
range, in this case 9. You are prompted for a value for *w*. Go
ahead and enter the string “aaaaabbbbb”, which is the smallest
string in the language where |*w*| ≥
*m*. (Tip: if you get a large value for *m*, such as 18,
and you wish for a smaller one, press “Clear All” repeatedly
until one is generated.) If for some reason you enter a string that
is either not in the language or where |*w*| < *m*, the
appropriate error message will appear in the *w* panel. When
finished, press enter, and the following two panels will become
visible.

The computer has chosen a decomposition
based on the *w* value that you entered. Now, given this
decomposition, it is your duty to choose an *i* value. Go ahead
and enter 13 for *i*. However, instead of progressing to the
next panel, the following error message should appear.

For all languages JFLAP supports, you
can only enter either 0 or a value between 2 and 12 for i. A value of
1 will result in a pumped string equal to *w*, and thus is
always in the language, so it is excluded. *i* values larger
than 12 are excluded so the pumped string doesn't get too large.
Thus, go ahead and enter 2 for *i*, which is in the permissible
range. When finished, the screen should resemble the one below. This
example is also available in regCompFirst.jff.

You've won, because the computer could
not choose a valid decomposition. In fact, as seen through the proof
earlier, it never will find one with this language, so you will
always win. Go ahead and make a few more attempts to familiarize
yourself with the format, however. You can enter a new *w* value
if you want to keep the same *m* value, or just press enter in
the *w* text box if you want to keep both values. You can enter
a new *i* value if you want to retain *m*, *w*, and
the decomposition. Panel visibility will adjust itself accordingly.

**This concludes
our brief tutorial on regular pumping lemmas. Thanks for reading!**