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.



1 Answer 1


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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