I was reading the proof of pumping lemma from Sipser's book. I couldn't understand certain things mentioned there.

pumping lemma proof

In the second paragraph he has written, "because $r_l$ occurs among first $p+1$ places, we have $l \le p+1$". Here, does $l$ denotes the number of states visited?

Also he wrote "We know that $j \neq l$, so $|y| > 0$; and $l \le p+1$; so $|xy| \le p$"

What I didn't understand is

  1. $j \neq l$

  2. $j \neq l$, so $|y| > 0$

  3. $l \le p+1$; so $|xy| \le p$


1 Answer 1


You missed what $j$ and $l$ are. Read the paragraph again. They are the two indices of the same state in the list of visited states. For example if some automata goes from $s_1$ to $s_3$ to $s_5$ to $s_3$ to $s_7$, then you could pick $j = 2$ and $l = 4$, because both $2$nd and $4$th elements in the sequence are $s_3$.

  1. They are always (and, assuming $n > p$, can always be) chosen different.
  2. $y$ was defined as the substring which takes $r_j$ to $r_l$. $j \neq l$ and you need at least one symbol to change state, hence $|y| > 0$.
  3. The substring $xy$ takes $r_1$ to $r_l$. A string of length $x$ visits $x+1$ states, so if we know that $xy$ visited $l \leq p+1$ states then $|xy| = l-1 \leq p$.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.