# Pumping Lemma for single character language [duplicate]

I have a question about the Pumping lemma. Condition $2$ of the pumping lemma for a string division $xyz$ states that the middle portion of the string $y^i$ can be 'pumped' for any $i$ greater than or equal to $0$. This means that y can be the empty string and yet still belong to the language. At the same time, the cardinality $|y|$ has to be at least $1$.

How would I be able to apply this if the regular language is only a single character? i.e. $L = \{a\}$. Here, I can set $y = \{a\}$ so that the cardinality is greater than zero --- however, it fails to meet the condition that $y$ can be 'pumped down' to the empty string....

But obviously, $L =\{a\}$ is a regular language.

And there's also something obvious that I missed ...

• Commented Aug 30, 2017 at 5:45
• If L is finite, so there exists a word z of maximal size k. If you construct an automata which accepts this word, you realize you need n=k+1 states. So the condition to find a word bigger n, |z|>=n, is not possible. But we need this word bigger than n, so we know there is some loop in the automata which can be pumped. And if you cannot fullfill the condition by such L, the implication of the pumping lemma is still valid. Commented Jan 24, 2021 at 11:56

You interpret the lemma incorrectly. The lemma says that "there is $n$ such that any string $y \in L$, with $|y| \geq n$...". So the lemma does not provide a particular $n$, it only says "there is", not "for all".

If the language is finite then, the pumping length is greater than the longest string in the language. And hence the three conditions of the lemma fails for all strings in the language, meaning there is nothing to "pump". Nevertheless, the lemma holds. Just recall the implication rule $p \implies q$: if $p$ is false then it does not matter if $q$ is true or false, the whole implication is true.

In your example with a single string $a$ take $n$, the pumping length to be $2$. So there is no string of the length greater than or equal to $2$. But it does not mean that the lemma fails.

Update:: the following predicate formula expresses the Pumping lemma for regular languages $$[ L \text{ is regular }] \implies [\exists n\forall x[ \left((x \in L) \land (|x| \geq n) \right) \implies (\exists u \exists uv \exists w(x=uvw \land |uv| \leq n \land |v| > 0 \land \forall m[m>0 \implies uv^mw \in L))]]]$$

and this is antecedent (conclusion) part of the lemma: $$\exists n \forall x[ \left((x \in L) \land (|x| \geq n) \right) \implies (\exists u \exists uv \exists w(x=uvw \land |uv| \leq n \land |v| > 0 \land \forall m[m>0 \implies uv^mw \in L))]]$$

This premise of the antecedent $(x \in L) \land (|x| \geq n)$ is false since $|x|$ is less than $n$ (for each $x \in L$) and hence the whole antecedent is true.

• Simpler explanation: $\forall x \in X. P(x)$ is true for all $P$ if $X = \emptyset$. Commented Aug 30, 2017 at 5:46
• @Raphael I edited as promised, now you can have a look at what I meant by premise. Commented Aug 30, 2017 at 21:10
• Thanks, you've made the issue explicit. "This premise of the antecedent (x∈L)∧(|x|≥n) is false" -- since the formula has a free variable, that statement doesn't make sense. You can't drop the quantification! (Note: you have now arrived at a longer form of my proposal of a "simpler explanation".) Commented Aug 31, 2017 at 4:38
• @Raphael I didnt drop I just showed you what part I meant. Just put there is and for all, and the premise evaluates to false for n larger than the length of the longest string. Commented Aug 31, 2017 at 4:44
• @Raphael by the way. Your "simple" explanation may mot work. I dont see how it applies to this case. Commented Aug 31, 2017 at 4:46