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?
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?