1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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




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...