# Does |xy| ≤ p in the pumping lemma count for all i?

While learning about the pumping lemma, I came across the following question:

Given the language L is $$a^n(0|1)^*$$ with $$c_0 \cdot c_1 = n$$, where $$c_0$$ indicates the amount of zeros present, use the pumping lemma to prove that this language is not regular. Examples of valid words in L are 0, 1, a01, aa001, etc...

In regular english: a word with leading as, followed by any amount of either 0 or 1 characters, where the amount of zeros multiplied by the amount of ones needs to match the amount of as.

My initial attempt was the following:

• Pick w as $$a^p0^p1$$. This obviously holds since $$p \cdot 1 = p$$.
• Split w into xyz as $$x = \epsilon$$, $$y = a^p$$, $$z = 0^p1$$.
• Show that $$xy^2z = a^{2p}0^p1$$ does not hold, since $$p \cdot 1 \ne 2p$$.

However, the answer key instead opts to introduce two new variables $$m \geq 0$$, $$n \gt 0$$, then splits on $$x = a^m$$, $$y = a^n$$, $$z = a^{p-n-m}0^p1$$ (splitting the sequence of a into three parts). Then, they too use $$i = 2$$ to show that $$xy^2z = a^{m}a^{2n}a^{p-n-m}0^p1 = a^{p+n}0^p1$$, which is not a member of the language (since n was more than 0).

As far as I can see, my attempt adheres to the $$|xy| \leq p$$ condition of the pumping lemma: x is empty and $$|y| = p$$. As such, I was under the impression that my answer was correct.

However, the huge increase in complexity of the answer in the answer key leads me to believe that this is not a valid approach. I have the sneaking suspicion this is because my answer actually does violate the $$|xy| \leq p$$ condition.

Is my attempt a correct way to prove that the language is not regular? If not, what misconception/mistake did I make along the way?

• I'm not sure what you mean by your title. The condition $|xy|\leq p$ doesn't depend on $i$: it's a fact about $x$, $y$ and $p$ only. – David Richerby May 20 '19 at 16:06

Your mistake is in the following step:

• Split $$w$$ into $$xyz$$ as $$x = \epsilon$$, $$y = a^p$$, $$z = 0^p 1$$.

You're not allowed to choose how $$w$$ splits into $$xyz$$. You should show that for any way of splitting $$w$$ into $$xyz$$ such that $$|xy| \leq p$$ and $$y \neq \epsilon$$, there exists $$i$$ such that $$xy^iz \notin L$$.

Here is a similar "proof" that the language $$01^*$$ isn't regular:

• Pick $$w$$ as $$01^p$$.
• Split $$w$$ into $$xyz$$ as $$x = \epsilon$$, $$y = 0$$, $$z = 1^p$$.
• Show that $$xy^2z = 0^21^p$$ is not in the language.

The proof of the pumping lemma will choose a different splitting, for example $$x = 0$$, $$y = 1$$, $$z = 1^{p-1}$$.

• Oh duh! Can't believe I forgot what is essentially the essence of the entire pumping lemma (showing that there's no way at all to satisfy it). Much love. – Peter May 20 '19 at 15:36