Pumping lemma for language that is regular

1
votes

I am trying to show how the pumping lemma applies to a language that is for sure regular. I have the language over {0, 1} that has an even number of 1's. This language can be represented by a DFA that has two states.

So the pumping length here is 2, correct? The pumping lemma states that "if s is any string in A of length at least p," then it may be divided into xyz such that the 3 PL conditions are true. So say we choose a string '000110' and want to show that somehow it can be split into xyz such that |xy| <= p (and |y| > 0, and x(y^i)z is in L).

In this case y would have to be '11' so that it can be repeated and still be even... which would make x = '000', right? This would then make |xy| = 5, which is more than p.

I don't see any other way of splitting the given string so that |xy| < p. What am I missing here? Thanks very much.

1
pumping-lemma
You could also pump '00'. – Jim Lewis
@JimLewis So I could make x = empty, y = '00' (or even '0'), and z = '0110'? – Greg Pete
Yes, both choices would satisfy the conditions of the PL. The key idea is that your choice of 'y' corresponds to a cycle in some DFA that recognizes the language. 'x' takes you to the first state in the cycle, 'y' takes you around the cycle, and 'z' takes you from the start of the cycle to some accepting state. – Jim Lewis

1 Answers

0
votes

@Jim Lewis provided the answer to my question - we can have x = empty string, y = '0' and a z of '00110', which will enabled us to pump y as much (or as little) as we want, satisfying the requirements of the pumping lemma. Thanks!