0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is not research-level $\endgroup$ – Hermann Gruber Feb 20 '19 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$ – Marzio De Biasi Feb 20 '19 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 '19 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$ – Marzio De Biasi Feb 20 '19 at 13:36
  • 1
    $\begingroup$ I found my answer here (cs.stackexchange.com/questions/1847/…). But thanks anyway. $\endgroup$ – stew.nesc Feb 20 '19 at 16:34
2
$\begingroup$

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

$\endgroup$

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