Let = {0, 1}, and consider the language L = {0 n 1u0 n | n 1, u }

The following problems relate to showing that L is not regular by using the Pumping Lemma. As explained in class, proving the of nonregularity of L using the Pumping Lemma requires one to find a word in L that generates, by regular iteration, words that are not in L. We must be able to do this for each choice of a pumping length p 1. Accordingly, suppose that someone (not you) chooses p 1. Now consider the string s = 0p 10p . For s to be a possible candidate string for generating counterexamples to the regularity of L, s must be in L and must be of length at least p. Obviously, |s| = 2p + 1, so s is of length at least p.

Now suppose that someone (not you) divides s into s = xyz such that |xy| p and |y| 1. You do not know anything about the exact division, only that the lengths of x and y satisfy the constraints |x| + |y| p and |y| 1.

The Pumping Lemma implies that if L is regular, then each string of the form xyi z for i 0 must be in L as well. This means that if any string of this form is not in L, then L cannot be regular. In this way s generates an infinite number of potential counterexamples to the regularity of L. We only need find one counterexample to show L is not regular.

5. Explain why xyi z is not in L