Pumping lemma for $a^n b^m a^{n+m}$

Question

I want to show that $L = \{a^n b^m a^{n+m} \mid n, m \geq 0\}$ is not regular.

Is it suffice to say that $a^0b^pa^p$ is in the language, then y = $a^k$ with 0 < k <= p, choose i = 0 so I get $a^{−k}b^pa^p$ which is not in the language?

Answer 1

You can’t do that, because $a^{-k}$ makes no sense. However, you can start with the word $w=b^pa^p$, where $p$ is the pumping length (on the assumption that $L$ is regular). The pumping lemma then says that $w$ can be decomposed as $xyz$, where $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for each $k\ge 0$. Clearly $xy$ must lie entirely within the initial substring $a^p$, so there are $i,j\ge 0$ such that $x=b^i$, $y=b^j$, and $j\ge 1$. Thus, for any $k\ge 0$ we must have

$$xy^kz=b^ib^{kj}z=b^{kj+i}z\;.$$

In particular, $xy^{p+1}z=b^{(p+1)j+i}z$, which is of the form $b^ma^p$ for some $m\ge(p+1)j+i\ge p+1$, and it’s clear that this word is not in $L$.