Context-Free Pumping Lemmas

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.

Definition

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 = uvⁱxyⁱz,

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

Explaining the Game

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ⁱxyⁱz is not a member of 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.

Starting the Game

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.

User Goes First

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ⁿbⁿ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.

Computer Goes First

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.