# Pumping lemma for regular languages [duplicate]

I have a vey specific question regarding the pumping lemma in the context of regular languages. The theorem states that if $$L$$ is a regular language, then there exists a constant $$n$$ such that for every string $$w$$ in L, with $$|w|\geq n$$, $$w$$ can be broken into $$w=xyz$$ with the following properties:

1. $$|y|>0$$

2. $$|xy|\leq n$$

3. For all $$k\geq 0$$, $$xy^kz \in L$$

My question concerns the third and first properties. In the third property, does $$k=0$$ not imply that $$|y|=0$$, therefore contradicting the first property? As far as I can tell, when $$k=0 \rightarrow xy^kz=xz$$ and, consequently, $$y=\epsilon$$. What am I missing?

How long is the word "cat"?

If I write "catcat", how long is the word "cat"?

If I write nothing at all, how long is the word "cat"?

• I love the way you explain. – John L. Mar 27 '19 at 21:44

In the third property, does $$k = 0$$ not imply that $$|y| = 0$$ , therefore contradicting the first property?

No, it does not.

The third item simply implies $$w' = xz \in L$$. If $$|w'| < n$$, then this does not contradict the lemma since it only holds for strings with length at least $$n$$. On the other hand, if $$|w'| \ge n$$, it means there are again substrings $$x', y', z'$$ with the conditions prescribed in the lemma (i.e., $$|y'| > 0$$, $$|x'y'| \le n$$, and $$x'(y')^k z' \in L$$ for all $$k \ge 0$$), but it does not at all imply $$x = x'$$, $$y = y'$$, nor $$z = z'$$, let alone $$w' = w$$.