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?

  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is not research-level $\endgroup$ Feb 20, 2019 at 6:17
  • $\begingroup$ 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$" :-) $\endgroup$ Feb 20, 2019 at 8:19
  • $\begingroup$ @MarzioDeBiasi or rather, it applies to all regular languages, but only words of sufficient length can be pumped. $\endgroup$
    – Aryeh
    Feb 20, 2019 at 12:35
  • $\begingroup$ @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 $\endgroup$ Feb 20, 2019 at 13:36
  • 1
    $\begingroup$ I found my answer here (cs.stackexchange.com/questions/1847/…). But thanks anyway. $\endgroup$
    – stew.nesc
    Feb 20, 2019 at 16:34

1 Answer 1


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


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