The language is $A = \{a^{n}b^{n}a^{m} : n \geq 0, m \geq 0, n \neq m\}$.
I tried to use the pumping lemma. I chose the string s = $a^p b^pa^{p + p!}$ that is split in $uvxyz$ and must respect
$|vy| > 0$
$|vxy| \leq p$
$uv^ixy^iz \in A, i \in \mathbb{N} $.
I can prove that for some i and $v$ or $y$ is anywhere in $a^pb^p$, the language is not context free. But I don't know how to prove when they are in the last $a$. Whatever $i$ is, this can be pumped. So, I think I chose the wrong s.
Any idea how to prove this?
Best Answer
I think that while the language may not be context-free (and it certainly doesn't look context-free), the pumping lemma cannot be used to prove it. It seems to me that you have put your finger on the difficulty. Let $s\in A$. Then $s=a^nb^na^m$ with $n\neq m.$ In the case that $n>m$ we can write $s=uvxyz$ where $$\begin{align} u&=a^n,\\v&=a,\\x&=\varepsilon,\\y&=b,\\z&=b^na^m\end{align}$$ Then for $i\geq0$,$$uv^ixy^iz=a^na^ib^ib^na^m=a^{n+i}b^{n+i}a^m\in L,$$ since $n+i>m$.
On the other hand, if $n<m$, we can write $s=uvxyz$ where $$\begin{align} u&=a^nb^na^m,\\ v&=a,\\ x&=\varepsilon,\\ y&=\varepsilon,\\ z&=\varepsilon \end{align}$$ and now for $i\geq0$,$$uv^ixy^iz=a^nb^na^ma^i=a^nb^na^ma^i=a^nb^na^{m+i}\in L,$$ since $n<m+i$.
Thus there is no string that we use can use for a pumping lemma proof.
The Wikipedia article on the pumping lemma states that there are alternatives to the pumping lemma for proving a language is not context-free. They mention Ogden's lemma and the interchange lemma, but I never studied either of these, so I can't be of much help. (Or not until I read up on them, at least.)
I found this example of the use of Ogden's lemma, which may be of use to you. I haven't found out enough about Ogden's lemma yet to understand the example myself.