So I am reading a book about Computational Theory, and I came across the Pumping Lemma. This is the formal definition of the lemma as stated in the book:

Let $A$ be a regular language. Then there exists an integer $p \geq 1$, called the pumping length, such that the following holds: Every string $s$ in $A$, with $|s| \geq p$, can be written as $s = xyz$, such that

  • $y \neq \epsilon$ (i.e., $|y| \geq 1$),
  • $|xy| \leq p$, and
  • for all $i \geq 0, xy^i z \in A$

So let the regular language be $A = \{101\}$. It is a regular language because there exists a Deterministic Finite Automaton that can accept this language, a simple straightforward one.

But, I don't see how the pumping lemma can hold for this regular language. Since there is only one string accepted, any $xy^iz$ with $i>1$ will not be a part of the language.

So the pumping lemma does not hold for all regular languages, but the formal definition seems to imply it does. What's the catch that I'm missing here? Thanks in advance :)

  • 2
    $\begingroup$ The pumping lemma does hold for this language (and for any finite language); here take $p$ to be $4$... $\endgroup$ Jul 15 '17 at 12:39
  • $\begingroup$ @LordSharktheUnknown is correct, but note that the lemma is vacuously true, since the integer p can be chosen larger than the longest string in any finite language. I'm not sure Shark's hint was sufficient. $\endgroup$
    – user2469
    Jul 15 '17 at 14:44
  • $\begingroup$ @barrycarter The definition clearly says $|s| \geq p$ so we can't choose p larger than the longest string. $\endgroup$ Jul 16 '17 at 17:05
  • $\begingroup$ Also, please elaborate more on what lord shark meant. I'm not yet 100% sure $\endgroup$ Jul 16 '17 at 17:06
  • $\begingroup$ Actually, it only says there exists an integer p with no restrictions on p. So, if we choose p=4, it's true that every string of length 4 or greater satisfies any condition, since there are no strings of length 4 or greater. It's a vacuous implication. If X never occurs, then X implies Y for any statement Y. $\endgroup$
    – user2469
    Jul 16 '17 at 17:31

Be careful with the quantifiers: the pumping lemma says that there exists some integer $p \geq 1$ such that whenever you pick a string $s$ from the language and that string has length greater than $p$, then the conditions in the lemma hold. In this case, we can therefore pick $p = 4$, because whenever you pick a string $s$ from the language, it will have length less than $p$, and thus we do not need to check the conditions.

In fact, this holds true for any finite language: simply pick $p$ to be the length of the longest string in the language plus one.


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.