<p>The pumping lemma states that if <span class="math-container">$L$</span> is a regular language, then there is an integer <span class="math-container">$p \geq 1$</span> (the "pumping length") such that every string <span class="math-container">$w$</span> in <span class="math-container">$L$</span> of length at least <span class="math-container">$p$</span> can be written as <span class="math-container">$w = xyz$</span> satisfying (1) <span class="math-container">$|y| \geq 1$</span>, (2) <span class="math-container">$|xy| \leq p$</span> and (3) <span class="math-container">$(\forall n \geq 0)[xy^nz \in L]$</span>.  (Source: <a href="https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement</a>)</p>

<p>If <span class="math-container">$L$</span> is finite, then one can take the pumping length <span class="math-container">$p$</span> to be any integer greater than the length of any string in <span class="math-container">$L$</span>.  The three conditions above would then be satisfied vacuously because there is no word in <span class="math-container">$L$</span> of length at least <span class="math-container">$p$</span>.  </p>

CC BY-SA 4.0
2019-02-20T05:16:58.570Z
2019-02-20T05:16:58.570Z
Zed
<p>It is said that "All finite languages are regular". </p>

<p>But the Pumping Lemma says that, </p>

<p><em>if a language is regular 
one can find a 'large-enough' word w such that it can be decomposed into w = xyz such that <strong>FOR ALL</strong> i >= 0 the word with a pumped up y^i is also in the language.</em> </p>

<p>But doesn't that state that "every regular language is infinite" since one can always infinitely (i in N) pump the word up and it will be still in the language? </p>

<p>So why are the finite languages regular and how are they fulfill the pumping lemma?</p>

CC BY-SA 4.0
2019-02-20T06:17:44.293Z
I'm voting to close this question as off-topic because it is not research-level
Hermann Gruber
CC BY-SA 4.0
2019-02-20T08:19:16.777Z
The pumping lemma applies only to infinite regular langauges. Exercise: look at the proof of the pumping lemma and see what is the issue with "$p$" :-)
Marzio De Biasi
CC BY-SA 4.0
2019-02-20T12:35:59.487Z
@MarzioDeBiasi or rather, it applies to *all* regular languages, but only words of sufficient length can be pumped.
Aryeh
CC BY-SA 4.0
2019-02-20T13:36:48.417Z
@Aryeh: yes you're right, it's more accurate; we can pick $p$ greater than the longest word in the finite language and everything is ok because the premise of the implication ( $|w| \geq p$ ) is false
Marzio De Biasi
CC BY-SA 4.0
2019-02-20T16:34:29.043Z
I found my answer here (https://cs.stackexchange.com/questions/1847/pumping-lemma-for-simple-finite-regular-languages). But thanks anyway.
stew.nesc
<regular-language>
Why are all finite languages regular?
stew.nesc
# Why are all finite languages regular?

(Asked by: username_0 on 2019-02-20)

It is said that "All finite languages are regular".

But the Pumping Lemma says that,

*if a language is regular
one can find a 'large-enough' word w such that it can be decomposed into w = xyz such that **FOR ALL** i >= 0 the word with a pumped up y^i is also in the language.*

But doesn't that state that "every regular language is infinite" since one can always infinitely (i in N) pump the word up and it will be still in the language?

So why are the finite languages regular and how are they fulfill the pumping lemma?

**Tags:** regular-language

> **Comments:**
> **username_1**: I'm voting to close this question as off-topic because it is not research-level  
> **username_2**: The pumping lemma applies only to infinite regular langauges. Exercise: look at the proof of the pumping lemma and see what is the issue with "$p$" :-)  
> **username_3**: @MarzioDeBiasi or rather, it applies to *all* regular languages, but only words of sufficient length can be pumped.  
> **username_2**: @username_3: yes you're right, it's more accurate; we can pick $p$ greater than the longest word in the finite language and everything is ok because the premise of the implication ( $|w| \geq p$ ) is false  
> **username_0**: I found my answer here (https://cs.stackexchange.com/questions/1847/pumping-lemma-for-simple-finite-regular-languages). But thanks anyway.  

---

## 1 answers

### Answer by username_4 on 2019-02-20. Score: 2

The pumping lemma states that if $L$ is a regular language, then there is an integer $p \geq 1$ (the "pumping length") such that every string $w$ in $L$ of length at least $p$ can be written as $w = xyz$ satisfying (1) $|y| \geq 1$, (2) $|xy| \leq p$ and (3) $(\forall n \geq 0)[xy^nz \in L]$. (Source: <https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement>)

If $L$ is finite, then one can take the pumping length $p$ to be any integer greater than the length of any string in $L$. The three conditions above would then be satisfied vacuously because there is no word in $L$ of length at least $p$.


---

