Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How can I prove, using the pumping lemma for context free languages, that $\{ll^{R}l|l\in\{a,b\}^{*}\}$is not a context free language ?

I tried to put $n$ as the pumping lemma constant and chose $a^{n}a^{n}a^{n}$ but this does seem to have a factorization since all I need is that the amount of $a$ in the word is divisible by $3$.

I then tried to take $l':=a^{n}b^{n}b^{n}a^{n}a^{n}b^{n}$ ($l=a^{n}b^{n})$, I am having a hard time even figuring out if this will lead to a contradiction:

My thoughts are that if $l'=uvwxy$ then since $|vwx|\leq n$ it must be contained in the $a^{n}$ or $b^{n}$ or be something like $a^{k_{1}}b^{k2}$ or $b^{k_{1}}a^{k2}$. but I'm having a difficult time continue from here, it seems that now I should go over each option and devide to options of how to factor it to $v,w,x$ which gives many cases.

Am I on the right path or can I do something easier/smarter ?

Please note: Since this is important to me, as this is how I prepare for my exam tomorrow (thus can't offer a bounty right now), I will give $50$ points (+upvote+accept) for a somewhat full solution of this question

share|cite|improve this question
up vote 1 down vote accepted

Try $l = b a^n b$, for some cutting $l l^R l = u v x y w z$ with $\lvert v x w \rvert \le n$ you have $u v^k x y^k z$ in your language. This requires that $bb$ is in $x$ (can't repeat it), and the $b$ starting the last $l$ falls outside the repeat anyway. Repeating $x$ and $y$ gives inflated $l$'s in the first part that are too long for the last untouched $l$.

This is just a rough outline, need to fill in many details.

share|cite|improve this answer
Minor nit: you have one too many variables in your decomposition $uvxywz$. It appears that you should have $uvxyz$ and $|vxy|\le n$. Nice answer, though---in my experience many people don't look for a way to pick the $x$ part so it can't be repeated. – Rick Decker Oct 12 '12 at 17:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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