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

Definition

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

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.

Explaining the Game

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

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 we need to choose a language. Let's try the first language on the screen, L = {aⁿbⁿ : 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.

Computer Goes First

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