1
$\begingroup$

Let L be a language. w $\in$ L , and w could be broken in xyz.

Then if L is regular, there exists a pumping length p such that:

  1. |y| $\gt$ 0
  2. |xy| $\le$ p
  3. $\forall$ i $\ge$ 0, xy$^i$z $\in$ L

I understand that this lemma is based on pigeon hole principle and proof by contradiction.

For conditon (1), I understand that the string we are pumping should be $\ge$ 1.

But I don't understand the significance of condition (2). Why should the legth of xy be equal to or smaller than p . Will not it work otherwise?

$\endgroup$
0
3
$\begingroup$

$p$ is the number of states in the automaton. As you say, the pumping lemma is about the pigeonhole principle. Suppose that $q$ is the first state that's repeated when you read input $w$. Then $x$ is the string that you read before you reach $q$ for the first time, and $y$ is the string you read between the first and second visits to $q$. Since there are only $p$ states including the start state, you must repeat a state after doing at most $p$ transitions, i.e., reading a string of length at most $p$. So the condition $|xy|\leq p$ comes from the proof.

In reality, when an automaton reads a particular string $w$, there might be many times when it returns to a state that has already been visited. If you take $w\in L$ any split $w=xyz$ with $|y|\geq 1$, such that the automaton is in the same state at the beginning and end of $y$ then $xy^iz$ will be in $L$ for all $i$, regardless of how long $xy$ is.

$\endgroup$
3
  • $\begingroup$ Thanks. Now it makes sense. Before repeating we have to visit at most p states. $\endgroup$ – rsonx Mar 31 '19 at 4:07
  • $\begingroup$ Does pumping lemma works for multi-loop automata? Lets say there are more than one loop. $\endgroup$ – rsonx Mar 31 '19 at 4:10
  • $\begingroup$ @Revolver Yes, it works for any automaton. The pigeonhole principle guarantees that there's at least one loop. More loops could only makes things "easier", but we can't exploit that, because we don't know for sure that any more loops exist. We just have to work with the one we can guarantee. $\endgroup$ – David Richerby Mar 31 '19 at 8:41

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