Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k}

Question

I had a question regarding the Pumping lemma for regular languages, I have been studying for an exam and came across the question {a^2k w | w ∈ {a, b}*, |w| = k}. In the website it lists the answer and I'm having a little bit of trouble trying to figure out what a specific part of this answer means. It states:

Assume L is regular. From the pumping lemma there exists a p such that every w ∈ L such that |w| ≥ p can be represented as x y z with |y|≠0 and |xy|≤ p. Let us choose a^2p b^p. Its length is 3p≥p. Since the length of xy cannot exceed p, y must be of the form a^k for some k > 0. From the pumping lemma a^2p-k b^p must also be in L but it is not of the right form since the number of a’s cannot be twice the number of b’s (Note that you must subtract not add , otherwise some a’s could be shifted into w). Hence the language is not regular.

So my issue lies in the very last line of the proof where it states that " you must subtract not add, otherwise some a's could be shifted into w"

Is there anyone that could help me visualize what this could possibly mean, I feel as though it may be trivial but I seem to be having trouble with it.

Thank you in advance!

Answer 1

In typical usage of the pumping lemma, you assume that the word you chose for pumping is written as $w=xyz$, with $x,y,z$ satisfying the conditions of the pumping lemma.

Then, in most cases, you reach a contradiction by saying that e.g., $xy^2z$ is not in the language. This is "pumping up", since you "add" copies of $y$.

In this case, however, you reach a contradiction by looking at the word $xz$ (i.e., $xy^0z$). So you are pumping "down", or subtracting copies of $y$.

The reason for this is that if you look at e.g., $xy^2z$, then you get a word of the form $a^{2p+k}b^p$, but this word might be written as $a^{2r} a^lb^p$ with $l+p=r$, so you would not reach a contradiction.