33
$\begingroup$

Wikipedia has the following definition of the pumping lemma for regular langauges...

Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1 depending only on $L$ such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w$ = $xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

  1. |$y$| ≥ 1
  2. |$xy$| ≤ $p$
  3. for all $i$ ≥ 0, $xy^iz$ ∈ $L$

I do not see how this is satisfied for a simple finite regular language. If I have an alphabet of {$a,b$} and regular expression $ab$ then $L$ consists of just the one word which is $a$ followed by $b$. I now want to see if my regular language satisfies the pumping lemma...

As nothing repeats in my regular expression the value of $y$ must be empty so that condition 3 is satisifed for all $i$. But if so then it fails condition 1 which says $y$ must be at least 1 in length!

If instead I let $y$ be either $a$, $b$ or $ab$ then it will satisfy condition 1 but fail condition 3 because it never actually repeats itself.

I am obviously missing something mind blowingly obvious. Which is?

$\endgroup$
1
  • 1
    $\begingroup$ You are missing that the lemma only states that strings at least $p$ long can be pumped. If there are no such strings, nothing can be pumped. In particular, for a finite language $p$ (the number of states in a DFA accepting the language, check the proof) is larger than the longest string in the language. $\endgroup$
    – vonbrand
    Feb 9, 2020 at 16:01

3 Answers 3

46
$\begingroup$

You are right - we cannot allow "pumping" words of a finite $L$. The thing you are missing is that the lemma says there exists a number $p$, but does not tell us the number.

All words longer than $p$ can be pumped, by the lemma. For a finite $L$, it happens so that $p$ is larger than the length of the longest word in $L$. Thus, the lemma only holds vacuously, and cannot be applied to any word in $L$, i.e., any word in $L$ does not satisfy the condition of "having length at least $p$" as the lemma requires.


A corollary: if $L$ has pumping length $p$, and there exists some word $w\in L$ of length at least $p$, then $L$ is infinite.

$\endgroup$
5
  • 5
    $\begingroup$ A nice instance of the empty set fulfilling $\forall$-statements. $\endgroup$
    – Raphael
    May 15, 2012 at 9:26
  • $\begingroup$ If |xy| <= p and all words longer than p can be pumped, then in practice |z| >= 1? $\endgroup$ May 20, 2021 at 20:34
  • 1
    $\begingroup$ @JoshHibschman Not necessarily. Consider the language defined by the regular expression $ab*$. For any such $w$ you can set $x=a, y=b^n, x=\epsilon$ when $|w| = n+1$. $\endgroup$
    – kviiri
    May 21, 2021 at 7:25
  • $\begingroup$ @kviiri can you describe a bit more? For example, set $n=1$ we have $ab$. $|w| = n+1 = 2$. Because all words longer than p can be pumped... $|w|$>p, $p=1$. Split $x=a$, $y=b$, it breaks the rule $|xy| <= p$ because $|xy|$ is 2 and p is 1. Same for p=2 (|w|=3). Aside, the min p is 2 because you can't pump down with p=1, right? $\endgroup$ May 21, 2021 at 20:51
  • $\begingroup$ @JoshHibschman Yes, $p=1$ is not valid for that language (the simplest counter-example would be that the string $a$ per se cannot be pumped in the language). $p=2$ however is valid, then you have $x=a, y=b, z=b^{n-1}$ for the string $ab^n$ for any $n \geq 1$. $\endgroup$
    – kviiri
    May 21, 2021 at 21:03
9
$\begingroup$

Pumping lemma is usually used on infinite languages, i.e. languages that contain infinite number of word. For any finite language $L$, since it can always be accepted by an DFA with finite number of state, $L$ must be regular.

According to wikipedia (http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement), pumping lemma says: $\begin{array}{l} (\forall L\subseteq \Sigma^*) \\ \quad (\mbox{regular}(L) \Rightarrow \\ \quad ((\exists p\geq 1) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\ \quad\quad ((\exists x,y,z \in \Sigma^*) (w=xyz \land (|y|\geq 1 \land |xy|\leq p \land (\forall i\geq 0)(xy^iz\in L)))))))) \end{array}$

For any finite language $L$, let $l_{max}$ be the max length of words in $L$, and let $p$ in pumping lemma be $l_{max}+1$. The pumping lemma holds since there are no words in $L$ whose length $\geq l_{max}+1$.

$\endgroup$
1
  • $\begingroup$ It does apply to finite languages just fine: The "pumping length" $p$ in those cases is just larger than the longest string in the language, thus there are no strings susceptible to pumping in the language. $\endgroup$
    – vonbrand
    Feb 15, 2020 at 16:25
3
$\begingroup$

One way to formalize the core part of the Pumping lemma is this, using $L^{\geq k} = \{ w \in L \mid |w| \geq k\}$:

If $L$ is regular, there exists $p \in \mathbb{N}$ so that

$\qquad \displaystyle \forall w \in L^{\geq p}.\ \exists x,y,z \dots$ (*).

For all finite $L$ and $p > \max \{ |w| \mid w \in L\}$, we have obviously that $L^{\geq p} = \emptyset$. Therefore (*) is (vacuously) true for such $p$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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