2
$\begingroup$

In this answer, it is told that the minimal $p$ value is $1$. One of the conditions of the pumping lemma is that

$|xy| \leq p$

Now if we try to split a string $01^p$, we might do it like this:

$x=\epsilon$, $y=01$, $z=01^{p-1}$

But this decomposition contradicts the above condition. If we arrive at a contradiction, then how $p$ can be equal $1$?

Besides, is there a maximum pumping length? Various sources define $p$ as constant, and if it is a constant, there should be a single value instead of minimum and maximum range.

$\endgroup$
3
$\begingroup$

The pumping length of a regular language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be split as $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) $xy^iz \in L$ for every $i \geq 0$. The pumping length of $(01)^*$ using this definition is $2$. Anybody claiming that the pumping length is $1$ is either wrong or has a different definition in mind (the notion of pumping length isn't completely standard, and my definition is not the only possible one).

In order to show that the pumping length cannot be $1$, you need to show that there exists some word $w \in L$ of length at least $1$ such that for every splitting $w = xyz$ in which $|xy| \leq 1$ and $y \neq \epsilon$ there exists $i$ such that $xy^iz \notin L$. In particular, you don't get to pick the decomposition. You need to show that no decomposition works. In this case, we can take the word $w = 01 \in L$. Since all words in $L$ have even length, if $w = xyz$ and $xz \in L$ then necessarily $y$ has even length. However, this is impossible since on the one hand $|y| \leq |xy| \leq 1$, and on the other hand $y \neq \epsilon$.

$\endgroup$
  • $\begingroup$ Thank you. That makes sense. What about the constant vs. variable value for $p$ question? $\endgroup$ – Dima Knivets Nov 10 '17 at 23:22
  • $\begingroup$ This question is a category error. The pumping length, as I have defined it, is a function of a language, which could be $\infty$ for non-regular languages. It is also not hard to check that if some value of $p$ satisfies the constraints (the part starting with "every word $w \in L$ of length at least $p$"), then any larger value of $p$ satisfies them. In that sense there is no "maximal" value of $p$. $\endgroup$ – Yuval Filmus Nov 10 '17 at 23:26
  • $\begingroup$ But that means that $p$ is not constant, right? $\endgroup$ – Dima Knivets Nov 10 '17 at 23:27
  • $\begingroup$ For every language, its pumping length is a "constant", just as $x^2$ is a constant for every value of $x$. For example, when $x=3$, $x^2$ is the constant 9. $\endgroup$ – Yuval Filmus Nov 10 '17 at 23:28
  • $\begingroup$ I assume that $p$ represents pumping length. In your previous comment, you mentioned that for strings larger than the $p$, we can use value higher than $p$ and the conditions would still be met, but that higher $p$ value would not be a pumping length, because pumping length is a function. Is my understanding correct? $\endgroup$ – Dima Knivets Nov 10 '17 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.