Problem Detail: I was reading the proof of pumping lemma from Sipser’s book. I couldn’t understand certain things mentioned there. 
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
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
- $j neq l$
- $j neq l$, so $|y| > 0$
- $l le p+1$; so $|xy| le p$
Asked By : user5507
Answered By : Karolis Juodelė
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$.
- They are always (and, assuming $n > p$, can always be) chosen different.
- $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$.
- 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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10577 Ask a Question Download Related Notes/Documents
