Question

I'm following one of the examples from my textbook on the Pumping Lemma:

Let C = {w | w has an equal number of 0s and 1s}

Condition 3 stipulates: |xy| <= p



If |xy| <= p, then y must consist only of 0s, so xyyz is not in C. 
Therefore s cannot be pumped

I'm having trouble understanding how condition 3 leads to the conclusion that "y must only consist of 0s, so xyyz is not in C"

Was it helpful?

Solution

I guess the string chosen is 0p1p. Since |xy| <= p, and xyz = 0p1p, the string xy will be 0k where k <= p since the first p symbols of 0p1p are all 0's. Since xy consists of only 0's, y must also consist of only 0's

And learn to put your question in a proper manner. You cannot expect others to "predict" your question while you put half of the information

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top