2
votes

So, I've been going through Sipser's book on the Theory of Computation, and one of the exercises is:

Let B be the language {0^n1^n | n≥0}.

Prove B is not regular.

The book continues to give a proof, using the pumping lemma, letting s=0^p 1^p, s=xyz and testing all three cases; when y is only 0's, only 1's, 0's and 1's. But I can't understand how the latter two options are possible by condition three of the pumping lemma |xy|≤p. Does this condition not imply that y can only be 0's?

1

1 Answers

2
votes

Does this condition not imply that y can only be 0's?

No, not necessarily. Fix p, and let the string be

w = xyz = 01/2 p11/2 p

What prevents x being the first character, z being the last, and y being everything in between?