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

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.

• Suppose you mark all the symbols. You're allowed to do that (which produces the pumping lemma). Now find a pumpable decomposition with no more than $p$ symbols. – rici Jul 1 '18 at 5:15
• You can do this using the pumping lemma. Use the condition $|vwx| \leq N$. – Yuval Filmus Jul 1 '18 at 6:28
• @rici this may be a misunderstanding of mine, but... i need to prove that for every possible decomposition of $z$ in $uvwxy$ there is a pumping that "push" $z$ out of $L$. – francesco bertolotti Jul 1 '18 at 7:13
• Possible duplicate of How to prove that a language is not context-free? – David Richerby Jul 5 '18 at 16:51

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.