How to use the pumping lemma to prove that $a^{m}b^{n}a^{m}c^n$ is not context free?

Question

How to use the pumping lemma to prove that $ Y = a^{m}b^{n}a^{m}c^n$ is not context free? Note that $m,n \ge 0$.

I tried by finding the case where it would be impossible for a word $w$ to be in $Y$. My problem is that I'm not sure about what I'm doing.

I think there are two cases to consider:

1. When the sub word $v$ or $y$ has different letter within it. Therefore, impossible for it to be in $Y$.
2. When the sub word $v$ or $y$ has only the same letters within itself. Because we have 4 different letters $a,b,a,c$ it is also impossible to encapsulate that in $|vxy|\leq p$.

The above assumption may be wrong. I need help with this because I barely understand how the pumping lemma works and how it works in this given problem.

Answer 1

I don't fully understand your proposed strategy, but I think you're on the right track. Let $\ p\ $ be the pumping length, and take $\ z=a^pb^pa^pc^p\in Y\ $. If $\ z=uvwxy\ $ with $\ |vwx|=q\le p\ $ and $\ |vx|\ge 1\ $, you can divide the possibilities for $\ u, vwx\ $ and $\ y\ $ into $7$ cases

1. $\ u=a^i, vwx=a^q, y=a^{p-i-q}b^pa^pc^p\ ,$$\ 0\le i\le p-q$;
2. $\ u=a^i, vwx=a^{p-i}b^{q+i-p}, y=b^{2p-q-i}a^pc^p,$$\ p-q<i< p$;
3. $\ u=a^pb^i, vwx=b^q, y=b^{p-i-q}a^pc^p,$$\ 0\le i\le p-q \ $;
4. $\ u=a^pb^i, vwx=b^{p-i}a^{q+i-p}, y=a^{2p-q-i}c^p,$$ p-q<i<p\ $;
5. $\ u=a^pb^pa^i, vwx=a^q, y=a^{p-q-i}c^p,$$\ 0\le i\le p-q\ $;
6. $\ u=a^pb^pa^i, vwx=a^{p-i}c^{q+i-p}, y=c^{2p-q-i},$$ p-q<i<p \ $;
7. $\ u=a^pb^pa^pc^i, vwx=c^q, y=c^{p-q-i},$$\ 0\le i\le p-q\ $.

If $\ n>1 $, then in the first case, $\ uv^nwx^ny=$$a^{p+n|vx|}b^pa^pc^p$$\not\in Y\ $, and in the second, $\ uv^nwx^ny=a^rb^sa^pc^p\ $ for some $\ r\ge p, s\ge p\ $ with $\ r+s>2p\ $, so again $\ uv^nwx^ny\not\in Y\ $. All the other cases can be handled similarly.