Why Does the Pumping Lemma Require |xy| ≤ p?

  • Thread starter Thread starter colt
  • Start date Start date
  • Tags Tags
    Condition
AI Thread Summary
The discussion revolves around the confusion regarding the Pumping Lemma's requirement that |xy| ≤ p, particularly in the context of a four-state DFA. The user questions why |x| can equal p when reaching the repetition state, suggesting that this leads to |xy| being greater than p. Clarification is sought on the specific Pumping Lemma being referenced and its proof. The user acknowledges the existence of multiple Pumping Lemmas and shares a screenshot of the proof for further analysis. The conversation highlights the need for a deeper understanding of the lemma's conditions and implications in automata theory.
colt
Messages
20
Reaction score
0
It says that |xy| < p. But I don't understand why even after reading the proof. If I have a four state DFA, whose last state is the one that is going to repeat for a given input string of length p, |x| is already going to be four, since it represents the states necessary to reach the repetition state. So in this worst case scenery, |x| is already equal to p, so with |y|>0 we already have |xy|>p. SO what's wrong with my line of thought
 
Mathematics news on Phys.org
If I understand correctly, the pumping lemma gives you a number, p, such that a bunch of stuff happens. Can you reference the exact pumping lemma you are talking about?
 
And show us the proof so we can understand.
 
I am sorry, I forgot that there is more than one pumping lemma so I aborted the copy that I was doing. Very clever from my part. Anyway I attached a screenshot of the proof:
 

Attachments

  • Screenshot.png
    Screenshot.png
    49.4 KB · Views: 451
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Thread 'Imaginary Pythagoras'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top