Register to reply 
Pumping lemma condition 3 
Share this thread: 
#1
Oct1613, 04:06 AM

P: 20

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 gonna repeat for a given input string of length p, x is already gonna 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



#2
Oct1613, 07:48 AM

P: 828

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?



#3
Oct1613, 02:08 PM

HW Helper
P: 1,713

And show us the proof so we can understand.



#4
Oct1613, 03:19 PM

P: 20

Pumping lemma condition 3
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:



Register to reply 
Related Discussions  
Context Free Languages, Pumping Lemma  Set Theory, Logic, Probability, Statistics  1  
Optical pumping  Atomic, Solid State, Comp. Physics  2  
Final condition instead of initial condition  Differential Equations  2  
Pumping Lemma Problem  Engineering, Comp Sci, & Technology Homework  0  
Pumping air over wing?  Mechanical Engineering  4 