0
$\begingroup$

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...

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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