In Sipser's Intro to Theory and computation, He writes: enter image description here

I don't understand the constraint on x. Shouldn't it be just y <=p? (Equal bc in the case when machine M runs through all states p) Making xy <=p, the theorem only wants us to consider the first p elements and the first repetiton. Why can't any repetition be considered for the pumping lemma? We can simply pick an arbitrary substring of length p and the looping structure works just fine? Is this constraint on x just to generalize since some inputs may not have more than one looping structure?

  • 1
    $\begingroup$ This additional constraint works in your favor. You’re free to ignore it. $\endgroup$ Commented Jul 15, 2019 at 0:09
  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – dkaeae
    Commented Jul 16, 2019 at 8:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.