Home
Up

JERIC 2004 paper

The Pumping Lemma for Regular Languages

Learning the Pumping Lemma

In order to learn how to apply the pumping lemma for regular languages to prove that some particular language is not regular, students must first have a firm understanding of the pumping lemma itself.  The applet shown below, and various versions thereof, allow students to explore a number of important concepts that lead to an understanding of this lemma:

1. Given a finite state automaton that recognizes some language, every input string that is at least as long as the number of states, n, in that fsa will cause the fsa to loop somewhere while processing the first n symbols of the string.
2. If the string being processed according to (1) is accepted by the fsa, the fsa will also accept strings with the substring that caused the loop removed from the original input string and with that substring repeated in the original input string.
3. There may be more than one loop-causing substring in the first n symbols of the input string.
4. Every substring of length at least n symbols in the original input string will force the fsa to loop.
5. In every case in which a substring of an accepted input string causes the fsa to loop, new strings can be created from the input string in which the loop causing substring is omitted or variously concatenated an arbitrary number of times in place in the string, and each new string thus created will also be accepted by the fsa.

Click here to view a tutorial.

System Requirements

Other than recent versions of the usual browsers and the Java Runtime Environment, no special software is needed to run this applet.

Acknowledgments

The applets demonstrated here are the work of Josh Cogliati and can be studied in more detail in his Master's thesis.