# How does a regular language satisfies the second condition of the pumping lemma

I'm a little bit confused about the second condition of the pumping lemma which are:

1. $$|y|\geq1$$
2. $$|xy|\leq p$$
3. $$\forall i \geq 0 : x y^i z \in L$$

I don't understand why the length of substrings $$xy$$ has to be less than the pumping length? Considering the example below:

Suppose we have a language $$L = \{ w | w ∈ 1^*0+1^*\}$$ and a string $$s \in L$$ which $$L$$ is a regular language.

Let the string $$s = 101$$ and $$S$$ can be split into three substring $$xyz$$ where $$y$$ can be pumped.

Therefore:

$$x = \text{'1'}$$ $$y=\text{'0'}$$ and $$z=\text{'1'}$$. It seems that substring $$|xy|$$ is somehow larger than the pumping length $$p$$ itself (in this case: $$p=1$$ since there's only one $$0$$), Therefore $$|xy| > p$$, a contradiction ! Does this mean that the language $$L$$ in this case is not regular ?

Or did I misunderstood something.

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Feb 8 '15 at 18:44

## 1 Answer

The pumping lemma states that if a language $$L$$ is regular then there exists $$p$$ such that every word $$w \in L$$ that is long enough ($$\lvert w \rvert \ge p$$) can be split as $$w = xyz$$ such that

1. $$|y| \geq 1$$.
2. $$|xy| \leq p$$.
3. For all $$i \geq 0$$, $$xy^iz \in L$$.

You give an example of a language $$L$$ and a string $$s \in L$$ which can be split as $$s = xyz$$ such that

1. $$|y| \geq 1$$.
2. $$|xy| = 2$$.
3. For all $$i \geq 0$$, $$xy^iz \in L$$.

This is a property which is similar to the one guaranteed by the pumping lemma, but perhaps different. The property expressed by the pumping lemma need not be the only property satisfied by a regular language. All the pumping lemma states is that if a language is regular then it satisfies the pumping property. It does not state that if a language is regular then the only property it satisfies is the pumping property.

To give an analog, consider the following statement: if $$x$$ is a multiple of $$4$$ then it is a multiple of $$2$$. Here is a "counterexample": $$12$$ is a multiple of $$4$$, but it is a multiple of $$3$$ (rather than $$2$$). Your counterexample is similar.

Another issue is the pumping length $$p$$. If you look at the proof, then $$p$$ is the size of a DFA accepting $$L$$. In particular, $$p$$ doesn't depend on $$w$$. In your case, it's not clear why you assume that $$p=1$$; in fact, when applying the pumping lemma, you cannot assume anything about $$p$$. You're just guaranteed that some $$p$$ exists. In fact, for your language $$p \geq 5$$, since the minimal DFA has $$5$$ states.

The condition $$|xy| \leq p$$ is supposed to help you apply the pumping lemma. For example, if you look at the language with strings $$0^n1^n2^m$$ for $$m, n \ge 0$$, without this condition you wouldn't be able to prove that the language is not regular, since the pumped part could always be in the $$2^m$$ area. The condition $$|xy| \leq p$$ allows you to locate the pumped part.

This condition isn't always general enough, for example it doesn't work for showing that $$2^m0^n1^n$$ is not regular. There is a more general version of the pumping lemma which can handle this called Ogden's lemma.