I am confused with even starting the proof. I understand the pumping lemma:

Let A be a language over $\Sigma$. If A is regular, then there exists $p > 0$ (pumping length) such that $∀s∈A$, if $|s|≥p$, then there exists $x,y,z∈ \Sigma^*$ such that $s = xyz$ and:

  1. $|y|>0$
  2. $|xy|≤p $
  3. $∀i∈ℕ x(y^i)z∈A$

What I am confused about is how does a computational trace end in a repeated state and have a length at most of length $|Q|$? How can I come about proving the statement using the pumping lemma?

enter image description here

  • 2
    $\begingroup$ Doing the exercise does not require the use of the pumping lemma. If anything, the exercise is part of the proof of the pumping lemma, as $|Q|$ will be the pumping length, and the "length at most $|Q|$" condition of the exercise becomes condition 2 in the pumping lemma. $\endgroup$ – angryavian Feb 14 at 4:58
  • $\begingroup$ This makes sense. My professor said that it would involve the use of the pumping lemma and I did not see it. I do see how it will be part of the proof though. Thanks! $\endgroup$ – Tom withers Feb 14 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.