Pumping lemma: why x in ∣xy∣ ≤ p?

Question

Looking at the pumping lemma, I've noticed that in the string $xy^pz$, there seems to be no rule explicitly stated for $x$ and $z$. If I understand correctly, $x$ and $z$ are basically anything on the 2 sides of the string $y^p$ that we're pumping and thus can be anything in $L$.

Rule 2 & 3 of the pumping lemma are:

• $|y| \geq 1$
• $|xy| \leq p$

Since $|x| = 0$ and $|z| = 0$ seem to be allowed, as they only need to be of non-negative length, we shouldn't need $x$ in rule 2 and it can be rewritten as $1 \leq |y| \leq p$.

Are $x$ and $y$ not just a substitute for whatever are on the 2 sides of $y^p$ which we're pumping? Why is $x$ in rule 2 if it doesn't seem to make a difference? If $x$ is necessary, why is there no $|yz| \leq p$?

Answer 1

You said:

If I understand correctly, $x$ and $z$ are basically anything on the 2 sides of the string $y^p$ that we're pumping and thus can be anything in 𝐿.

This is not true. The pumping lemma suggests that for every long enough word $w$ such that $w\in L$, there is a partition of $w$ into three words $w = xyz$ such that the three conditions of the lemma hold. You only know that such $x, y$ and $z$ exist, you do not know whether this is true for all $x, y, $ and $z$ that partition $w$. Thus, you cannot force $x$ or $z$ to be empty. In fact, this is far from being true. For example, consider the language of the regex $a b^*$. Here $y$ cannot contain the letter $a$, thus you cannot force $x$ to be the empty word.

You also said:

If $x$ is necessary, why is there no $|yz|\leq p$?

This condition is too strong as, along with the condition on $|xy|$, it suggests that every long enough word $w$ in the language, has to be of length at most $2p$, which is not correct. Also, once you have the condition $|xy|\leq p$, there is no need to have a condition on $|yz|$. The pumping lemma conditions come up naturally from how a run of length at least $|Q|+1$ looks. In such long runs, two states have to repeat in the first $|Q|+1$ states of the run, and thus the condition on $|xy|$ arises. You can think about considering the last $|Q|+1$ states in a long run, and that might give you another variant of the pumping lemma (where $x$ and $z$ replace rules) but I don't see how this may be more useful or more appealing than the standard pumping lemma.

Answer 2

I think it might be useful to understand where the pumping lemma comes from and how it can be proven.

If a language $L$ is regular, there exists a DFA that recognizes it$^1%$.
Let $p$ be the number of states in the DFA.
As a word passes through it, the automaton goes through a sequence of states, as each symbol is consumed.
For a word $w$, if $|w| \ge p$, then this sequence comprises at least $p + 1$ states, so it necessarily contains at least a duplicate.
The sequence might contain multiple distinct states that are repeated an arbitrary number of times, but we choose to focus only on the first state that gets repeated and its first repetition (i.e. second occurrence).

So for these long words, their state sequence looks like this:
$q_1, q_2, ... q_n, q_r, q_{r+1}, ... q_{r+m}, q_r, ... q_l\ ^2$
With the following properties:

• $q_1$ is the initial state
• $\forall i, j \in [1, n], (i \neq j) \iff (q_i \neq q_j)$ (first n states are distinct)
• $\forall i \in [1,n], q_i \neq q_r$
• $\forall j \in [1,m], q_{r+j} \neq q_r$
• $q_l$ is a final state

We choose to name three parts of the word:

• $x$ is the first part that is consumed through a sequence of states without repetition, i.e. whatever is consumed by going through $q_1, q_2, ..., q_n, q_r$
• $y$ is the part consumed between the first state that is ever repeated and its first repetition (or second occurrence), i.e. whatever is consumed by going through $q_r, q_{r+1}, ... q_{r+m}, q_r$
• $z$ is whatever's left, the part consumed after going through the second occurrence of $q_r$

From here we can extract all the conditions of the lemma:

• $|y| \ge 1$ - the smallest possible sequence for $y$ is $q_r, q_r$; a transition from $q_r$ back to itself; in a DFA, each transition must consume a symbol
• $\forall k \in \mathbb{N}, xy^kz \in L$
  • for $k = 0$ simply delete everything from $q_r$ to $q_{r+m}$; you're left with a valid sequence of states ending in a final state; so whatever word is consumed by it is in the language
  • similarly, you can replace the second $q_r$ with $q_r, q_{r+1}, ..., q_{r+m}, q_r$ as many times as you want
• $|xy| \le p$ - we said we're only interested in the first state to be repeated and its first duplication; so in $q_1, q_2, ..., q_n, q_r, q_{r+1}, ... q_{r+m}, q_r$ each state is unique except for $q_r$, so the sequence has length at most $p + 1$, standing for the consumption of at most $p$ symbols.

This third condition is the one relevant to your question; it is true that $1 \le y \le p$ and that can be inferred from it. But $|xy| \le p$ is a stronger condition that we can prove, so why wouldn't we employ it?

As for what we can say about $|yz|$ - pretty much nothing from the above. You could make a change in the proof and instead of focusing on "the first repeated state and its first duplication", you could instead pick "the last repeated state and its last duplication", which would give you $|yz| \le p$; but doing so, you would lose the part about $|xy|$ - you can't have both$^3$. Why the pumping lemma is as it is, it's probably just cultural and somewhat arbitrary.

---

$^1$ there actually exists an infinitude of DFAs that recognize it, as you can always add unreachable dummy states. However, things get simpler if we choose to only be interested in the minimal DFA - the one with the smallest number of states.

$^2$ The names $q_1, q_2$ etc. do not refer to the actual names of the states, it's just a way to refer to them in the context of this sequence; $n$ and $m$ are some natural numbers, with the only restriction that $n + m \le p - 1$

$^3$ There's a difference between the two pumping lemmas with conditions $|xy| \le p$ versus $|yz| \le p$ and a pumping lemma with a condition $|xy| \le p\ or\ |yz| \le p$ - while the disjunction one would hold for the same languages, it would require more (unnecessary effort) in its employment

Answer 3

The condition $|xy|\leq p$ requires that the selected substring $y$ to be pumped is not too far from the start of the string.

Consider the language $L = \{x |x \in \{0,1\}^* x\ has\ equal\ number\ of\ 0's\ and\ 1's \}$ which can be shown to be a non-regular language via the pumping lemma. To show that this is not regular the usual example string used is $0^p1^p$. With the 2nd condition, no matter how we divide this string, we only get 0's for $y$, so the lemma fails for this. If we just require $1 \leq|y|\leq p$ then we are free to select anywhere in the substring, say $y = 0^{p/2}1^{p/2}$ and pump the substring and pass the lemma.

The requirement of selecting $y$ not to be far from the start of the string has something to do with the proof that the pumping lemma exists in the first place. So you might want to check it out from some book like Sipser or whatever you are using or here.

Edit: I decided to give my own explanation in case you do not want to read the references

In the proof of the pumping lemma, given some regular language $L$, $p$ is the number of states of the smallest DFA that recognizes $L$. Say that there exists $w\in L$ such that $|w| \geq p$. Remember that before we even begin consuming $w$, we are already at the start state so technically we have already entered 1 state and there are $p-1$ remaining states that we have not entered yet. But $w$ contains $\geq p$ symbols and reading a symbol will result to entering a state, so it must be that at least one state was entered more that once. This is where the pigeonhole principle is applied.

From above, it must be that the sequence of states entered to consume $w$, from the initial to the final state, contains a cycle. Now, string $w=xyz$ because $x$ represents the substring consumed before entering the cycle, $y$ is the substring consumed in the cycle, and $z$ is the consumed after the cycle.

Given a language $L$ and a string $w$ from it, you do not necessarily need to find the smallest DFA to get $p$. It is known to be there, assuming that $L$ is regular. What you are trying to do is to guess a correct partition of $w$. Finding the correct partition is equivalent to finding the state $q_i$ where the cycle will begin. Of course, when you find $q_i$ you cannot start the DFA there since you must begin at the start state (unless of course $q_i$ is the start state which implies that $|x|=0$). So your simplified bound of $1 \leq y \leq p$ is not enough. Essentially, the substring $x$ is like your offset from the start state to $q_i$. Since there are at most $p$ states, and you are initially at the start state, you can try to visit at most $p-1$ states until you find $q_i$ which implies that the length of $x$ is at most $p-1$. Since $|y| \geq 1$, the length of $xy \leq p$