Pumping Lemma: contraddiction between y ≠ ε and k ≥ 0

Pumping Lemma: contraddiction between y ≠ ε and k ≥ 0

by FRANCESCO VEZZANI -
Number of replies: 4

In the context of the pumping lemma for regular languages, one of the conditions is that y ≠ ε, meaning  |y| > 0 . However, the lemma also allows for the string to be pumped for any  k ≥ 0 , which includes  k = 0 . 

When  k = 0 , we would expect  y^0 = ε, meaning y effectively “disappears” from the string, reducing the expression  xy^kz  to  xz .

Could someone help clarify why it works if there is a contradiction ? 

**Attached there is a photo of my summary notes, please check if my reasoning are wrong. 

Tags:
In reply to FRANCESCO VEZZANI

Re: Pumping Lemma: contraddiction between y ≠ ε and k ≥ 0

by GIOVANNI GAIO -
There is no contradiction, and your reasoning is correct.

The special case of the lemma with k=0 is in no way contradictory, it just tells you that actually if xyz is in a regular language, then also xz is in the same language, but is a shorter string (possibly even with |xz|<n).

The hypothesis that y ≠ ε is needed because if you don't include it, the Pumping lemma would be trivial: it would just tell you that if xεz is in a regular language then xε^kz is also in that language for all k≥0.

I hope this helps (and I didn't miss something).
In reply to FRANCESCO VEZZANI

Re: Pumping Lemma: contraddiction between y ≠ ε and k ≥ 0

by Giorgio Satta -

I agree with Giovanni.

Another way of looking into this is as follows. The conditions on \( y \)  in the pumping lemma are meant to explain how you should cut the string \( w \). The statement about the iteration using \( k \) is a different matter: it specifies how to generate new strings starting given the cut you have chosen.

I hope this is clear now.