1
$\begingroup$

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

1 Answers 1

1

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.

  • 2
    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.2012-10-12