Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pumping lemma condition 3

  1. Oct 16, 2013 #1
    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. jcsd
  3. Oct 16, 2013 #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?
     
  4. Oct 16, 2013 #3

    verty

    User Avatar
    Homework Helper

    And show us the proof so we can understand.
     
  5. Oct 16, 2013 #4
    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:
     

    Attached Files:

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted
Similar Discussions: Pumping lemma condition 3
  1. Konig Lemma (Replies: 2)

  2. Ito's Lemma (Replies: 6)

  3. What is a lemma? (Replies: 4)

Loading...