15.2.1 The Pumping Lemma

The most common way to prove that a language is regular is to actually build a regular expression for the language. In doing this we can rely on the fact that the regular languages are closed under union, concatenation, Kleene star, complementation, and intersection. We saw examples of union, concatenation, and Kleene star in Ch. 2. So if we can independently build a regular expression for two distinct parts of a language, we can use the union operator to build a regular expression for the whole language, proving that the language is regular.

Sometimes we want to prove that a given language is not regular. An extremely useful tool for doing this is the Pumping Lemma. There are two intuitions behind this lemma. (Our description of the pumping lemma draws from Lewis and Papadimitriou (1988) and Hopcroft and Ullman (1979).) First, if a language can be modeled by a finite automaton with a finite number of states, we must be able to decide with a bounded amount of memory whether any string was in the language or not. This amount of memory can be different for different automata, but for a given automaton it can't

grow larger for different strings (since a given automaton has a fixed number of states). Thus the memory needs must not be proportional to the length of the input. This means for example that languages like $ a^n b^n $ are not likely to be regular, since we would need some way to remember what $ n $ was in order to make sure that there were an equal number of $ a $'s and $ b $'s. The second intuition relies on the fact that if a regular language has any long strings (longer than the number of states in the automaton), there must be some sort of loop in the automaton for the language. We can use this fact by showing that if a language doesn't have such a loop, then it can't be regular.

Let's consider a language $L$ and the corresponding deterministic FSA $M$, which has $N$ states. Consider an input string also of length $N$. The machine starts out in state $q_0$; after seeing 1 symbol it will be in state $q_1$; after $N$ symbols it will be in state $q_n$. In other words, a string of length $N$ will go through $N+1$ states (from $q_0$ to $q_N$). But there are only $N$ states in the machine. This means that at least two of the states along the accepting path (call them $q_i$ and $q_j$) must be the same. In other words, somewhere on an accepting path from the initial to final state, there must be a loop. Fig. 15.3 shows an illustration of this point. Let $x$ be the string of symbols that the machine reads on going from the initial state $q_0$ to the beginning of the loop $q_i$. $y$ is the string of symbols that the machine reads in going through the loop. $z$ is the string of symbols from the end of the loop ($q_j$) to the final accepting state ($q_N$).

The machine accepts the concatenation of these three strings of symbols, that is, xyz. But if the machine accepts xyz it must accept xz! This is because the machine could just skip the loop in processing xz. Furthermore, the machine could also go around the loop any number of times; thus it must also accept xyyz, xyyzz, xyyyyz, and so on. In fact, it must accept any string of the form $ xy^n z $ for $ n \geq 0 $.

The version of the pumping lemma we give is a simplified one for infinite regular languages; stronger versions can be stated that also apply to finite languages, but this one gives the flavor of this class of lemmas:

Pumping Lemma. Let $L$ be an infinite regular language. Then there are strings $x, y$, and $z$, such that $y \neq \epsilon$ and $xy^n z \in L$ for $n \geq 0$.

The pumping lemma states that if a language is regular, then there is some string y that can be “pumped” appropriately. But this doesn’t mean that if we can pump some string y, the language must be regular. Non-regular languages may also have strings

that can be pumped. Thus the lemma is not used for showing that a language is regular. Rather it is used for showing that a language isn't regular, by showing that in some language there is no possible string that can be pumped in the appropriate way.

Let's use the pumping lemma to show that the language $ a^n b^n $ (i.e., the language consisting of strings of as followed by an equal number of bs) is not regular. We must show that any possible string s that we pick cannot be divided up into three parts x, y, and z such that y can be pumped. Given a random string s from $ a^n b^n $, we can distinguish three ways of breaking s up, and show that no matter which way we pick, we cannot find some y that can be pumped:

1. y is composed only of as. (This implies that x is all as too, and z contains all the bs, perhaps preceded by some as.) But if y is all as, that means $ xy^n z $ has more as than xyz. But this means it has more as than bs, and so cannot be a member of the language $ a^n b^n! $

2. y is composed only of bs. The problem here is similar to case 1; If y is all bs, that means $ xy^{n}z $ has more bs than xyz, and hence has more bs than as.

3. y is composed of both as and bs (this implies that x is only as, while z is only bs). This means that $ xy^n z $ must have some bs before as, and again cannot be a member of the language $ a^n b^n! $

Thus there is no string in $ a^n b^n $ that can be divided into x, y, z in such a way that y can be pumped, and hence $ a^n b^n $ is not a regular language.

But while $ a^n b^n $ is not a regular language, it is a context-free language. In fact, the context-free grammar that models $ a^n b^n $ only takes two rules! Here they are:

$$ S\ \to\ a\ S\ b $$

$$ S\to\epsilon $$

Here's a sample parse tree using this grammar to derive the sentence aabb:

There is also a pumping lemma for context-free languages, that can be used whether or not a language is context-free; complete discussions can be found in Hopcroft and Ullman (1979) and Partee et al. (1990).