High Level Explanation of the Pumping Lemma

Question

I have a problem that I cannot figure out regarding using the pumping lemma to prove that a language is not regular. I don't understand how I go about proving through contradiction that the language is not regular.

When I read about the pumping lemma, all I am finding are complicated explanations involving $x$, $y$, $z$ and $m$ which seems difficult to understand.

I would appreciate if someone could provide a high level overview of the pumping lemma, and possible an example of proving a language is not regular with its use.

Answer 1

The context of the FSA pumping lemma is a very common one in computer science. The origin goes to the fact that we use finite definitions to represent infinite object, or collection of objects of unbounded size, such as infinite sets of strings.

In a discrete world, such as the syntax of mathematics, the only way you can go arbitrarily far in the confined space of a finite definition is by going repeatedly trough the same steps. That is why we use induction, loops and recursion.

The kernel of the problem

To take the simplest example, the only way you can make an arbitrarily long walk on a finite directed graph is by going several time through the same node. And that implies that you have a loop, at least one.

Of course, if the way you measure your walk is by the number of encounters of a specific feature, a milestone, that may not appear everywhere, then an arbitrarily long walk implies that you have a loop with at least one such milestone.

Actually, you do not even have to consider arbitrarily long walks. It is enough to consider a walk that is strictly longer than the number of milestones, a walk of length $n+1$ if there are $n$ milestones. Then you necessarily encounter twice the same milestone (pigeon hole principle). Hence there is a loop with that milestone, and possibly others.

So, consider a finite directed graph with $n$ milestones. We choose a number $p \geq n+1$ (called the pumping length).

Any walk in that graph that encounters at least $p$ milestones has necessarily gone through a loop, at some point, when it encounters the $p^{th}$ milestone.

Let us call $u$ the part of the walk before entering the loop, $v$ the part of the walk inisde the loop, and $w$ the remaining end of the walk. We then know the following:

• The loop $v$ contains at least one milestone. We note $|v|$ the number of milestones it contains. Hence $|v|\geq 1$.

• The loop does not necessarily include the $p^{th}$ milestone. But may occur before it. Whatever the case may be, the total length of the beginning $u$ of the walk (of length $|u|$ milestones) and one run through the loop ($|v|$ milestones) must have occured when the $p^{th}$ milestone is passed. Hence $|u|+|v|\leq p$, i.e. $|uv|\leq p$.

• Since there is a loop $u$ that you have walked at least once, nothing prevents you from going around it as many times as you want, $i$ times for any integer $i$, before finishing the $w$ part of your walk. You could also be in a hurry and decide to skip the loop, finishing the $w$ part just after doing the beginning $u$ of the walk, which amounts to having $i=0$.

Using the usual concatenation notation, your walk can be $uv^iw$ for any integer $i\geq 0$.

Automata theory jargon is that you can pump the loop $v$ as many times as you want in your walk, and you can even pump it out once if you wish (when $i=0$).

This is the heart of the pumping lemma. It can then be translated in various forms, for different kinds of formalisms, and with variations to help prove theorems.

Note that most often, you use the lemma to prove that no such $p$ can exist. So do not worry too much about what its value may be. The way proofs work is by assuming there is such a number $p$ as required by the pumping lemma. Then you show that it leads to some contradiction, so that you have a problem or structure that cannot be pumped. And this proves that your problem or structure is not in some pumpable family. (see proof techniques)

For example, regular languages are in a pumpable family, with proper interpretation of the basic construction.

Pumping regular languages.

In the case of regular languages, the graph is the FSA diagram. However, the milestones are painted with colors, which are the symbols of the input alphabet, and our walk fragment $u$, $v$, and $w$ are represented by sequences of symbols read on the milestones, one milestone for each symbol on the FSA diagram.

Actually we have proved more than the traditional pumping lemma for FSA. For example, we can decide that some symbols are not part of the milestones count. That still works, but does no more than applying an erasing substitution, which does preserve the regular character of a language. But we might possibly try other such games, possibly more subtle ... which I have not done yet ... I just wrote this.

Answer 2

By definition, a language is regular if, and only if, it is accepted by a deterministic finite automaton (DFA). So, given a language $L$, suppose it is accepted by some DFA $M$. $M$ has some number of states: let's call it $p$. Now, consider the operation of $M$ on a string $w\in L$ that has length greater than $p$.

If $M$ accepts $L$, then it must accept $w$. By the pigeonhole principle, there must be at least one state $q$ that $M$ visits twice. Write $w=xyz$, where $x$ is the sequence of characters that $M$ reads until it first reaches $q$, $y$ is the sequence of characters read between the first and second visits to $q$ and $z$ is the rest of $w$. Note that $y$ must be at least one character, since it occurs between the first and second visit to $q$, which are different positions in the input. Observe that:

• from the initial state, reading $x$ takes you to state $q$;
• from state $q$, reading $y$ takes you back to $q$;
• from state $q$, reading $z$ takes you to an accepting state.

The key point is that, from $q$, reading $y$ any number of times, including zero, will return you to state $q$ and you can then read $z$ to get to an accepting state. Therefore, the machine $M$ accepts any string of the form $xy^rz$ for $r\geq 0$. We have just proved the pumping lemma.

For examples of using the pumping lemma, see our reference question. In essence, you say, "If this language was regular, it would have to obey the pumping lemma. But if it did that, it would have to include all of these strings that it doesn't include. Therefore, it's not regular."