# Proving a language is not regular using Pumping Lemma

So I am given the language qr where q is any combination of a's and b's. r is then the reverse of whatever q is. For example, abba is in the language because we can make a q = ab and r = ba

I have to prove, using the Pumping Lemma, that this language is not regular.

I can't make any sense of this, because it seems apparent that with xyz, we can set x = z = ε. Then we can just fit the entire expression into y. So for example, y = abba.

It doesn't matter how many times we repeat this, it will always be in the language.

• With 2 repetitions, abbaabba has q = abba and r = abba.
• With 3 repetitions, abbaabbaabba has q = abbaab r = baabba

This will always hold because since r is a repetition of q, the produced string by pumping will always be divisible by 2 in a way where the middle perfectly creates q, r | r = REVERSE(q)

What am I missing? Thank you for any help...

In the case of the pumping lemma, it is not good for intuition or practice to consider specific strings, such as $$abba$$. The statement of the pumping lemma says that if a language $$L$$ is regular, then every single string $$w \in L$$ of length at least $$p$$ can be written as $$w = xyz$$ satisfying
1. $$|y| \geq 1$$
2. $$|xy| \leq p$$
3. for every $$n \geq 0$$, $$xy^nz \in L$$.
So your proof should go something like this: in order to derive a contradiction, assume that $$L$$ is regular. Then let $$p$$ be the length given by the pumping lemma. Consider the string $$s = a^pb^pb^pa^p$$. Now for the important part: since $$s \in L$$, the pumping lemma guarantees that $$s$$ can be partitioned into $$xyz$$ satisfying the conditions above. In particular, since $$|xy| \leq p$$ and $$|y| > 0$$, it must be that $$y$$ consists only of $$a$$'s. Thus, we can pump up (or down) and the string will no longer be in $$L$$.
This is a contradiction so our initial assumption (that $$L$$ was regular) must be false. Therefore $$L$$ is not regular.