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*.

Before continuing, it is recommended that if you read the tutorial for regular pumping lemmas if you haven't already done so. It explains many of the basics of the game, both when the user goes first and when the computer goes first. This tutorial will primarily focus on those features which differentiate between context-free and regular pumping lemmas.

JFLAP defines a context-free pumping lemma to be the following.
Let *L* be an infinite context-free 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* = *uvxyz*,

with

|*vxy*| ≤ *m*,

and

|*vy*| ≥ 1,

such that

*w _{i}* =

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

JFLAP treats the context-free pumping lemma in a two-player game.
In the game below, Player A is trying to find a *uvxyz*
decomposition that is always in the language no matter what the *i*
value is. 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 context-free. 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*uvxyz*such that |*vxy*| ≥*m*and |*vy*| ≥ 1.Player B picks an integer

*i*such that*uv*is not a member of^{i}xy^{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 context-free pumping lemma game, select **Context-Free
Pumping Lemma** from the main menu:

The following screen should come up. It has the same functionality as the corresponding screen for regular pumping lemmas, except this time it includes some languages which are context-free and some that are not.

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, let's choose the first language in the list, L
= {a^{n}b^{n}c^{n,} : n ≥ 0}. Go ahead and
press the “Select” button to the right of the language. The
following screen should come up.

You may notice that the left panel resembles the screen
that we used for regular pumping lemmas. You may also wonder about
the right panel, which is the case panel. Not all the languages
listed use this panel, and the left panel takes up the whole screen
for those that do not. However, this one does utilize it, and we will
interact with it in time. First, however, play the game that is
identical to the one played with regular pumping lemmas, except that
instead of composing into *xyz* you will decompose into *uvxyz*.
Use a value of 3 for *m* and a decomposition of *u* = “aa”,
*v* = “a”, *x* = “b”, *y *= ”b”, and *z*
= “bccc”. When finished, your screen should resemble the one
below.

We failed to find an adequate decomposition this time.
However, we have checked one possible case for out decomposition,
which is when *v* has at least one “a” and “b” and when
*y* has a “b”. In many of the context-free languages
supported by JFLAP (although not all of them), the languages support
the storage and implementation of cases. This language is one of
them. Thus, we can add the case that we have chosen to the case panel
on the right. Click on the “Add” button, and a new line
representing this case should become visible in the right panel.

You should also notice that all the buttons at the bottom of the case panel are now visible. What each button does is as follows:

“Add” will add the current attempt to the case panel if the attempt represents a new case. If the case is already listed in the case panel, you are informed with a message in the text box above the buttons that that case resembles an existing case in the panel (telling you the number).

“Replace” will replace the attempt stored in the highlighted case with the current attempt. Since there is only one case at present, it is already highlighted, but if there were more, you can highlight them by clicking on the relevant case with the mouse. If the current attempt is an invalid example of a particular case, you will be informed of that fact.

“Show” will show on the left panel the current attempt stored in the highlighted case.

“Delete” will remove the highlighted case from the case panel.

“Clear” will remove all cases from the case panel.

“Done?” will inform you either how many cases are absent from the case panel or whether all cases are present.

“List” will list all the cases that have yet to be generated, with preset attempts stored in them.

Certain buttons will be visible at different times, depending on
whether an action is legal at that moment in time. Also note that if
you choose a new *m *value, then all cases will be removed from
the panel. This is due to the fact that the stored attempts may no
longer be valid with a new *w* string. One should also note that
if a case example does not generate a valid partition, then all
examples of that case will not necessarily do likewise. It is
possible, but not for every language, so one must use intuition
before generalizing one example to an entire case.

Below is the screen for when all eleven cases in this language are present in the case panel. The file with this screen present is stored in cfUserFirst.jff.

Context-free pumping lemmas when the computer goes
first have similar functionality to the corresponding regular pumping
lemma mode, except with a *uvxyz* decomposition. No cases are
used for when the computer goes first, as it is rarely optimal for
the computer to choose a decomposition based on cases. Thus, the case
panel will never be present.

**This
concludes our brief tutorial on context-free pumping lemmas. Thanks
for reading!**