# Why does the Pumping Lemma Constraint |xy| ≤ p mean that y can't be 1 in the string 0p1p

I am trying to get my head around the Pumping Lemma to prove a language is non-regular.

I am reading the Sipser text book and he gives the following example.

Let B be the language $$\{0^n 1^n | n \ge 0\}$$

Let $$s = 0^p 1^p$$

I understand that the idea is you can split this string into xyz such that y can be pumped. It is the constraint of $$|xy| \le p$$ that is confusing me.

Sipser notes that due to this constraint y could not equal 01 nor could it equal 1. Why would y equaling either of those values violate the given constraint.

I am generally quite confused by the Pumping Lemma so any general advice or good resources you can recommend, I would appreciate.

Thanks!

## 1 Answer

Let $$p$$ be the pumping length of your language. As you say, the string $$s$$ can be written as $$s = xyz$$ where $$|xy| \le p$$. By the choice of $$s=0^p 1^p$$, you know that the first $$p$$ characters of $$s$$ are all $$0$$, therefore $$xy$$ (which contains at most $$p$$ character) must be a string containing only $$0$$s. Since $$y$$ is a suffix of $$xy$$, $$y$$ must also contain only $$0$$s.

• Hi thanks for your answer. I had become blinkered and completely overlooked the fact that the length of the string was 2p. – Jack27696 Feb 7 at 22:22