[Solved]: Pumping Lemma for regular languages proof doubt - Sipser Book

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

1. $j \neq l$

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

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

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10577

 Ask a Question

 Download Related Notes/Documents