Pumping lemma (context-free) of $L = \{a^nb^{\max\{n,m\}}a^m\ |\ n, m ≥ 0\}$

Question

I want to show that $L = \{a^nb^{\max\{n,m\}}a^m\ |\ n, m ≥ 0\}$ is not context-free.

I tried with things like take $w=a^pb^pa^p$ and got that $vwz$ is $a^qb^{p-q}$ but... I don't know, it doesn't seem right to me.

Answer 1

If $p$ is the pumping length, let $w=a^pb^pa^p$. If $L$ is context-free, it is possible to write $w=uvxyz$ in such a way that $|vy|\ge 1$, $|vxy|\le p$, and $uv^kxy^kz\in L$ for every integer $k\ge 0$. Now consider cases.

• If $vxy$ lies entirely within the block of $b$s or one of the blocks of $a$s, $uv^2xy^2z\notin L$: if $vxy$ lies in one of the $a$ blocks, $uv^2xy^2z$ has too few $b$s, and if it lies in the $b$ block, $uv^2xy^2z$ has too many $b$s.
• If $vxy$ contains both $a$s and $b$s, then $uxz\notin L$, because it contains too few $b$s. (Always remember that it’s possible to pump down, by setting $k=0$, as well as up.)