Pumping Lemma proof $L= \{a^nb^m2^{n*m} \mid m,n \ge 0 \} $ not regular

Question

I'm trying to proof that the following language is not a regular language using the pumping lemma:

$L= \{a^nb^m2^{n*m} \mid m,n \ge 0 \} $

I tried to build the string by assuming that m,n are the same number p, $w = 0^p1^p2^{p^2}$. but I'm stuck with what should I do next?

I know how to solve for example the problem $L= \{0^n1^n \mid n \ge 0 \} $. I read many times the theorem:

If $L$ is regular, we are able to divide $w$ up into three parts $s=xyz$ where:

$|xy|\leq p$,

$|y| > 0$,

$xyz \in L \Leftrightarrow xy^{i}z\in L $ for all $i\in\mathbb{N}$

I would be very grateful if somebody will help me

Answer 1

Your choice of $w$ works. If $w=xyz$, where $|xy|\le p$ and $|y|>0$, then $xy$ is contained in the $0^p$ part of $w$. In fact, there are $r\ge 0$ and $s\ge 1$ such that $x=0^r$, $y=0^s$, and $r+s\le p$. Then $z=0^{p-r-s}1^p2^{p^2}$,

$$\begin{align*} xy^iz&=0^r0^{si}0^{p-r-s}1^p2^{p^2}\\ &=0^{r+si+p-r-s}1^p2^{p^2}\\ &=0^{p+(i-1)s}1^p2^{p^2}\,. \end{align*}$$

This is in $L$ if and only if $p\big(p+(i-1)s\big)=p^2$, which is true if and only if $p(i-1)s=0$, and since neither $p$ nor $s$ is $0$, that is true if and only if $i=1$. Thus, any change in $i$ away from $1$ gives you a word not in $L$, which therefore isn’t regular.

Note that you could have started with the simpler word $w=0^p12^p$ and made essentially the same argument.

Answer 2

Alternatively, one may use Myhill-Nerode (which I am aware is not being asked in the question, but I usually find much cleaner!):

Consider the set of strings $s_i = ab^i$, where $i \geq 0$.

Then if $i \neq j$, $s_i \cdot 2^i = ab^i 2^i$ is in the language, but $s_j \cdot 2^i = ab^j 2^i$ is not. Therefore, $2^i$ distinguishes $s_i$ and $s_j$, so there are infinitely many equivalence classes.