Search code examples
regular-languageautomatacomputation-theory

Using condition 3 of the pumping lemma to prove irregularity


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?


Solution

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