1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ $x$ and $y$ seem to be symmetrical. Why would they not have the same assumptions and rules? $\endgroup$ – John Zhau Jan 4 at 12:13
  • 2
    $\begingroup$ I don't see how $x$ and $y$ seem symmetrical. Can you elaborate? The pumping lemma suggests that there exist $x, y$ and $z$ that satisfy some non-symmetrical conditions. $\endgroup$ – Bader Abu Radi Jan 4 at 12:25
  • 1
    $\begingroup$ @JohnZhau Perhaps you should take another look at the formulation of pumping lemma. For example here: cs.stackexchange.com/questions/133900/… and then note that the conditions hold for some $x, y, z$, and not for all $x, y, z$. Once you grasp the formulation of the lemma. Try to see the proof of the pumping lemma here, for example: en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages It would clarify to you alot of things. $\endgroup$ – Bader Abu Radi Jan 4 at 13:03
  • $\begingroup$ I meant $x$ and $z$ seem symmetrical. Typo. $\endgroup$ – John Zhau Jan 5 at 0:58
  • 2
    $\begingroup$ In that sense, you're right. One can prove that there is a partition of $w$ into $w = xyz$ such that: 1) $|y| > 0$. 2) $|yz|\leq p$, and $xy^iz \in L$. This simply follows by modifying the proof to consider the suffix of length $|Q|+1$ of a run, instead of its prefix. As I mentioned in the answer, this could be another variant of the pumping lemma, yet there is no good reason to prefer it over the standard formulation. $\endgroup$ – Bader Abu Radi Jan 5 at 11:57
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
4
  • $\begingroup$ From what I've read, we can choose any sub-strings to use the pumping lemma on. What exactly do you mean "not too far from the start"? How far is too far? $\endgroup$ – John Zhau Jan 4 at 12:12
  • $\begingroup$ @JohnZhau, I tried to expand my answer, hopefully it will make things clearer. I did not discuss the case of $z$ since it is only for the excess string after the cycle $\endgroup$ – Russel Jan 4 at 13:15
  • $\begingroup$ I do read wikipedia. The problem is that, like many university math professors, wikipedia is not made to explain things simple for laymen and is often more suited for people already with more knowledge on the subject. It's precise but not intuitive and easy to understand... $\endgroup$ – John Zhau Jan 5 at 2:24
  • $\begingroup$ @JohnZhau I try to make my additional discussion as simple as possible. Just ask if there is something that is still not clear $\endgroup$ – Russel Jan 5 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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