8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Raphael Sep 23 '16 at 7:48
10
$\begingroup$

It's not needed for the proof. You can prove the lemma without this condition. Adding this condition makes the statement stronger and so more useful.

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Just to clarify a bit more, unless |xy| is less than or equal to p, does it mean that we have visited more than p states but we have not repeated any of them? Where the last condition is physically impossible. $\endgroup$ – Masroor Sep 23 '16 at 5:56
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Sep 23 '16 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.