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

  • Thread starter Thread starter colt
  • Start date Start date
  • Tags Tags
    Condition
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: 448

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

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...
View full post »

Thread 'Fermat's Last Theorem'

Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
View full post »

Thread 'Useless continued fraction for 1'

I'm interested to know whether the equation $$1 = 2 - \frac{1}{2 - \frac{1}{2 - \cdots}}$$ is true or not. It can be shown easily that if the continued fraction converges, it cannot converge to anything else than 1. It seems that if the continued fraction converges, the convergence is very slow. The apparent slowness of the convergence makes it difficult to estimate the presence of true convergence numerically. At the moment I don't know whether this converges or not.
View full post »

Similar threads

MHB Proving L is not Regular using Pumping Lemma
Replies
1
Views
2K
B Golden Ratio in Collatz-like sequences
Replies
1
Views
2K
MHB Show that the language is not context-free with the Pumping Lemma
Replies
6
Views
5K
I Homemorphism in quotient topology
Replies
5
Views
547
I Probability: why can we use the Dirac delta function for a conditional pdf?
Replies
12
Views
4K
Conditions for the X dot P expectation to be constant?
Replies
9
Views
2K
I Counterexample Required (Standard Notations)
Replies
16
Views
3K
MHB Why do we conclude that p|exactly one of b0,c0?
Replies
3
Views
2K
I Empirical temperature scales using different thermometers
Replies
7
Views
2K
Properties of Derivations and of Tangent Vectors
Replies
4
Views
3K

Hot Threads

Recent Insights

Back
Top