2
$\begingroup$

This question already has an answer here:

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

$\endgroup$

marked as duplicate by Yuval Filmus formal-languages Aug 30 '17 at 7:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Simpler explanation: $\forall x \in X. P(x)$ is true for all $P$ if $X = \emptyset$. $\endgroup$ – Raphael Aug 30 '17 at 5:46
  • $\begingroup$ @Raphael I edited as promised, now you can have a look at what I meant by premise. $\endgroup$ – fade2black Aug 30 '17 at 21:10
  • $\begingroup$ 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".) $\endgroup$ – Raphael Aug 31 '17 at 4:38
  • $\begingroup$ @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. $\endgroup$ – fade2black Aug 31 '17 at 4:44
  • $\begingroup$ @Raphael by the way. Your "simple" explanation may mot work. I dont see how it applies to this case. $\endgroup$ – fade2black Aug 31 '17 at 4:46

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