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