Cheap and Secure Web Hosting Provider : See Now

[Solved]: Intuition behind the condition |xy| ≤ p in pumping lemma for regular languages

, , No Comments
Problem Detail: 

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

Asked By : Masroor

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63790

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback