Context-Free Pumping Lemmas


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,


|vxy| ≤ m,


|vy| ≥ 1,

such that

wi = uvixyiz,

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:

  1. Player A picks an integer for m.

  2. Player B picks a string w such that w is a member of L and |w| ≥ m.

  3. Player A picks the partition of w into uvxyz such that |vxy| ≥ m and |vy| ≥ 1.

  4. Player B picks an integer i such that uvixyiz 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 = {anbncn, : 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:

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.

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