How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?

Question

I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help.

The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should choose which symbols to mark.

I tried with all the first $N$ $a$s (and also other combinations), but then for $v=a^j$ and $x=a^j$ (and $w=b^{N+1}$) pumping doesn't get a string out of $L$. My idea is that I should involve both $a$s and $b$s between the marked symbols and somehow force the pumping for both, but I don't know how.

Answer 1

Let $N$ be the constant of the Pumping Lemma for CFL.

Let be $z=a^N b^{N+1} a^N b^{N+1}$.

let's analyze some of the possible decompositions of $z$ in $uvwxy$:

(note that $vx$ has always at least one symbol)

1. $u=\epsilon$, $v=a^*$, $w=a^*$, $x=a^*$, $y=b^{N+1} a^N b^{N+1}$. just pumping once we get a string out of $L$.
2. $u=a^*$, $v=a^*$, $w=a^*$, $x=a^*$, $y=b^{N+1} a^N b^{N+1}$. same as above.
3. $u=a^*$, $v=a^*$, $w=a^*$, $x=a^*b^*$, $y=b^* a^N b^{N+1}$. same.
4. $u=a^*$, $v=a^*$, $w=a^*$, $x=b^*$, $y=b^* a^N b^{N+1}$. same.
5. $u=a^*$, $v=a^*$, $w=a^*b^*$, $x=b^*a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
6. $u=a^*$, $v=a^*$, $w=a^*b^{N+1}$, $x=a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
7. $u=a^*$, $v=a^*$, $w=b^{N+1}$, $x=a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
8. $...$

Anyway the problematic case is 7. because it could be $u=a^k$, $v=a^j$, $w=b^{N+1}$, $x=a^j$, $y=a^kb^{N+1}$ with $k+j=N$, so that pumping doesn't push $z$ out of $L$. But again, it can't happen otherwise we would have $\mid vwx\mid >N$, which is not possible and it is guaranteed by the lemma.