1
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\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 Feb 7 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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