# Pumping lemma for simple finite regular languages

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?

• 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. Feb 9, 2020 at 16:01

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.

• A nice instance of the empty set fulfilling $\forall$-statements.
– Raphael
May 15, 2012 at 9:26
• If |xy| <= p and all words longer than p can be pumped, then in practice |z| >= 1? May 20, 2021 at 20:34
• @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$. May 21, 2021 at 7:25
• @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? May 21, 2021 at 20:51
• @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$. May 21, 2021 at 21:03

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$.

• 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. Feb 15, 2020 at 16:25

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$$.