18
$\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$
28
$\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$
  • 2
    $\begingroup$ A nice instance of the empty set fulfilling $\forall$-statements. $\endgroup$ – Raphael May 15 '12 at 9:26
7
$\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$
2
$\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$

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.