Prove $\left\{u \# v | u,v \in \{0,1\}^{*} \text{ and } u \text{ is a substring of } v \right\}$ is not context free

Question

I'm practising for my CS exam and got stuck on this problem

$\left\{u \# v | u,v \in \{0,1\}^{*} \text{ and } u \text{ is a substring of } v \right\}$

So I've tried using following pumping lemma:

Pumping Lemma would be: $0^n1^n\#0^n1^n$. 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 $0^n1^n$, then $v^2$ and $x^2$ will make it longer than the R.H.S.;

However I'm not really sure how to proceed here, since u is a substring I believe the N on RHS must be lower than on LHS, am I going about it the right way or not?

Answer 1

I’m assuming that your $n$ is the pumping length, and that you’re suppose that $0^n1^n\#0^n1^n$ can be decomposed as $uvwxy$ so that $|vwx|\le n$, $|vx|\ge 1$, and $uv^kwx^ky\in L$ for all $k\ge 0$, where $L$ is the language in question. This will work, but there are several cases to be considered.

• If $vwx$ is contained in the first $0^n1^n$, taking $k=2$ gives you a word $z_1\#z_2$ with $|z_1|>|z_2|$, and such a word cannot be in $L$.
• If $vwx$ is contained in the second $0^n1^n$, taking $k=0$ gives you a word that is not in $L$ for the same reason.
• If the $\#$ is in $vx$, any $k\ne 1$ gives you a word that is not in $L$, since it does not have exactly one $\#$.

Those cover what you’ve already done.

Now show that the only other possibility is that $v=1^p$, $w=1^q\#0^r$, and $x=0^s$ for some $p,q,r,s\ge 0$ such that $p+q+r+s\le p$, and $p+s\ge 1$. Then split this into two case, $p\ne 0$ and $p=0$. In each case there is a way to choose $k$ so that $uv^kwx^ky\notin L$ for the same kind of reason that we’ve seen before.