1
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by xskxzr, Discrete lizard Apr 28 at 12:18

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.

4
$\begingroup$

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"?

$\endgroup$
  • 2
    $\begingroup$ I love the way you explain. $\endgroup$ – Apass.Jack Mar 27 at 21:44
3
$\begingroup$

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

$\endgroup$

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