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

  • Context: Graduate 
  • 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
 
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: 501

Similar threads

  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 12 ·
Replies
12
Views
6K
  • · Replies 16 ·
Replies
16
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 0 ·
Replies
0
Views
4K
  • · Replies 3 ·
Replies
3
Views
5K
  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 5 ·
Replies
5
Views
5K
  • · Replies 3 ·
Replies
3
Views
2K