[Solved]: High Level Explanation of the Pumping Lemma

Problem Detail: 

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.

Asked By : Rusty

Answered By : babou

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32213

3.2K people like this

 Download Related Notes/Documents