Showing that u#v with u a substring of v is not context-free

Question

I need to find whether this language is context-free or not:

{u#v | u,v belong to {a,b,c}* and u is a substring of v}, over alphabet {a,b,c,#}

I suspect that it's not, and am trying to approach it via Pumping Lemma, but then I noticed that: any examples like a^n#a^n will not work, cos we can always make vwx in the second a^n such that after pumping, u is still a substring of v; then I tried playing around with # like a#ab^(n-3), but get lost with the choice of v and x since it's possible for one of them to be empty string.

This is homework so just a hint will be okay for me.

Answer 1

Okay I got confused when developing my ideas, and a simple example using Pumping Lemma would be: $a^nb^n\#a^nb^n$. Consider this: clearly $v$ and $x$ cannot contain $\#$, otherwise when pumping more or less $\#$ appear and the new string is not in the language. Now suppose $vwx$ are in the left $a^nb^n$, then $v^2$ and $x^2$ will make it longer than the R.H.S.; then if $vwx$ are in the right $a^nb^n$, then $v^0x^0$ will make the R.H.S. shorter than the left. This gives us the only possibility that $v$ in the first $b^n$ and $x$ in the second $a^n$, and clearly no matter how you pump it the new string cannot be in the same language, and this solves the problem.