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:

• $|y|\geq1$

• $|xy|\leq p$

• $\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.

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

• $|y| \geq 1$.

• $|xy| \leq p$.

• 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

• $|y| \geq 1$.

• $|xy| = 2$.

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

StackExchange Computer Science Q#38120, answer score: 7