Pumping lemma condition 3

  • Thread starter colt
  • Start date
  • #1
22
0

Main Question or Discussion Point

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
 

Answers and Replies

  • #2
828
2
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
verty
Homework Helper
2,164
198
And show us the proof so we can understand.
 
  • #4
22
0
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

Related Threads on Pumping lemma condition 3

  • Last Post
Replies
4
Views
631
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
21
Views
4K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
1
Views
2K
Replies
13
Views
990
Top