Physical significance of pumping length in pumping lemma

Question

Would it be possible to explain the physical significance of pumping length $p$ in pumping lemma for regular languages?

Somehow, the physical significance of pumping length $p$ in pumping lemma for regular languages escapes me.

I have explored a number of tutorials and presentations on this topic. The nearest I came to is, at some point, $p$ was assumed to be the number of states in the DFA recognizing the language. But the same presentation at some later point cautioned that $p$ is a property of the language, and not of the DFA.

When we prove a language to be not-regular, first of all, we assume it to be regular and thus having a pumping length $p$. We also assume the language to satisfy the conditions of pumping lemma. Later on, we find that the language fails to satisfy the conditions of pumping lemma and hence not a regular one.

So, such languages will not have any pumping length.

But what about regular languages? If I am given a regular language, there are many, just pick any one from this list, $10^*$, $1\Sigma^*$, $\Sigma^* 001$, would it be possible for us to point out the pumping length for that language?

Answer 1

First, in the Pumping Lemma as I know it, there is no such thing as the pumping length for a language. "For every regular language $L$ there exits a constant $p$ such that for any string $w\in L$ with $|w|\ge p$ ...". In fact, if $L$ satisfies pumping length $p$ then it will also satisfy any pumping length larger than $p$. (This is not completely trivial, the requirements in the dots ... above mention $p$ again.)

So we can call the smallest length $p$ for which the pumping property holds "the" pumping length. This is indeed a property of the language. If I am right the pumping length for $L = a(aa)^*+b(bb)^*$ is three. Strings of length 3 and above can be "pumped".

As you observe yourself, every regular language can be pumped (well, that is what the Lemma states). And the proof may use any automaton for the language. Whenever a string is at least as long as the number of states in the automaton, its computation must repeat a state, and we can pump. We can use the smallest automaton for the language, to minimize the pumping length. That smallest deterministic automaton is in fact well-defined. Unfortunately this in general still does not fix the (minimal) pumping length. An automaton for $L$ above seems to use at least five states (and actually 6 if it must be deterministic).

But still the property seems tied to the regular language via a certain "minimal" automaton, and the length of strings that ensure repetition of states.

But hey, even non-regular languages might in fact be pumpable: the Pumping Lemma (or better Pumping Property) is not a characterization of the regular languages. See for instance "Languages that satisfy the pumping lemma but aren't regular?" where it is observed that languages of the form $c L\cup \{ c^k \mid k\neq 1 \}\cdot\{a,b\}^∗$ for any $L\subseteq \{a,b\}^*$ have the Pumping Property (for pumping length one or two, I believe). I do not know a "physical" significance in the nonregular case.

Answer 2

Thinking of the pumping length as the size of a DFA recognizing the language is a good intuition. If you want to be more precise, you need to be careful about quantifiers.

A pumping length that works in a proof that the language is regular is the number of states in a DFA recognizing the language. $p$ is not unique. It's always possible to build a DFA with more states (trivially, by adding unreachable states or separating equivalent dead states, or in more complex ways). And if the pumping property is true for a certain $p_0$, it's true for all $p$ such that $p \ge p_0$.

It follows that the minimum pumping length that works for the lemma is smaller or equal to the minimum size of a DFA recognizing the language. The minimum pumping length is sometimes, but not always equal to the minimum DFA size. This is to be expected since the pumping lemma is not an equivalence — a language which is not regular, but for which the pumping property holds, has in a sense a finite pumping length but an infinite minimum finite automaton size. Hendrik Jan gives some examples.

The minimum pumping length is a property of the language, and not of the DFA, since it's about the words that are recognized by the language and not about how these words are recognized. It isn't about a specific DFA recognizing the language, but you could say that it's about the class of DFA's that recognize that language.

Answer 3

Regular languages that are infinite may nevertheless include a finite set of (possibly very large) strings that will not be produced by cycling, or any sort of repetitive pattern. The pumping length allows you to abstract these singularities in the formulation of the pumping lemma.

As it happens, the correctness of the lemma is guaranteed by a pumping length that is bigger than - for instance - the largest non-cycling sequence of transitions of a minimal DFA, but it is not necessary (or particularly interesting) to define it in these terms. As you noted, being regular is a property of the language, not of any particular way of defining it.