# Intuition behind the condition |xy| ≤ p in pumping lemma for regular languages

When I take a look at the proofs for pumping lemma, I have a feeling that I am often missing the intuition behind the condition |xy| ≤ p.

What exactly is the reason behind this condition? All the literature I have taken a look at are either silent (no proof, no discussion, only a statement) about this point, or state that we want the first repetition to occur not too far from the start.

But when there is an inequality involved, with very precise symbols and operators, don't we expect there to be a clear proof where we ultimately reach this condition?

What I am looking for are,

1. Mathematical proof for the condition, |xy| ≤ p.
2. Intuition behind the same condition.

To make the strings sufficiently long we have the condition string size at least p. My specific issue is why it is needed that |xy| ≤ p? And what does it break if |xy| ≤ p is not true?

(What's the reason for the second condition of the pumping lemma(s)?, does not exacly answer my question. The question is perhaps alright, but the answers only give some examples without much deep intuition.)

• Apparently you need to look at better proofs and/or the proofs more closely. The constant $p$ is usually derived very explicitly, and this process is intimiately tied to the "meaning" of $xy$. Maybe you are looking for "deep intuition" where there really is none... – Raphael Sep 23 '16 at 7:48

The intuition here is that if a DFA has $p$ states and there is a list of $p+1$ of them, then the list must contain two states which are the same. The string $x$ is the part that stretches from the beginning of the input to the first occurrence of the double state, and the string $y$ stretches until the second occurrence. By considering the first repeat we can guarantee that $|xy| \leq p$, since after reading $p$ characters we have seen $p+1$ states.
• Yes, that's the idea. For that to work, you need to choose the very first repeat of a state when you define $x$ and $y$. – Yuval Filmus Sep 23 '16 at 5:58