1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.