patternMinor
Physical significance of pumping length in pumping lemma
Viewed 0 times
significancelengthpumpinglemmaphysical
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#83089, answer score: 4
Revisions (0)
No revisions yet.