L ={ $a^{m^n}$ | $m$>$n$ } is Regular or not by pumping Lemma [duplicate]

Question

L ={ $a^{m^n}$ | $m$>$n$ }
I am bit confuse whether to consider this language as L = $(a^{m})^{n}$ OR L = $a^{\left(m^n\right)}$.

If it is considered as L = $(a^m)^{n}$ then want to check it is Regular or not by Pumping Lemma.
I tried by following way.

$m$ > $n$ so we can take $m's$ value as $n+1$.
So $L$ = $(a^{n+1})^{n}$

Let n be the Pumping Lemma Constant.
Then by pumping Lemma $u$$v^{i}$$w$ in $L$ for every $i$ $>=$ $0$.

$1<= |v| <= n$

$uv <= n$.

So here $u$ = $(a^{n+1})^{n-1}$

$v$ = $(a^{n+1})^{i}$ and

w = $\epsilon$

By taking $i = 2$ ,
I am getting string as $(a^{n+1})^{n+1}$Which is not possible. Because it means $m=n$.
So above string is not Regular.

But different solutions giving different answers. So confused whether it is Regular or not. And is there any problem in my solution ?

Answer 1

Let $A = \{ m^n : m > n \}$, so that $L = \{a^k : k \in A\}$. It is not clear whether $m,n \geq 0$ or $m,n > 0$. In both cases, every $m > 2$ is in $A$ and $0 \notin A$. If $m,n > 0$ then $1 \notin A$, while if $m,n \geq 0$ then $1 \in A$. In the former case, $L = aa^+$, and in the latter, $L = a^+$. In both cases $L$ is actually regular.

We can also consider the other interpretation, $A = \{mn : m > n\}$; this interpretation is wrong, but it can shed light on your proof. Again we find that every $m > 2$ is in $A$, and that $1 \notin A$. If $m,n$ are allowed to be zero then $0 \in A$, and otherwise $0 \notin A$. In the former case $L = aa^+ + \epsilon$, and in the latter, $L = aa^+$. In both cases $L$ is regular. So something must have been wrong with your proof.

Answer 2

The problem is poorly worded. There are two possible interpretations:

First, if the interpretation was $L=\{a^{(m^n)}\mid m>n\ge 0\}$, then notice that $a^i\in L$ for any $i>0$, (by choosing $m=i, n=1$ or, if $i=1$ choose $n=0$) so $L=\{a^i\mid i\ge1\}$ which is regular. Similarly, if the interpretation was $L=\{a^{(m^n)}\mid m>n> 0\}$, then we'd have $L=\{a^i\mid i>1\}$, which is also regular.

Having ruled out that reading, the alternative is that $L=\{(a^m)^n\mid m>n\}$ where we might have $n>0$ or $n\ge 0$. The choice is immaterial. Note that $(a^m)^n=a^{mn}$ and @lucas has noted in the comments, that means that $L=\{a^{mn}\mid m\ne m\}$ but this is just the complement of the language $\{a^{(p^2)}\mid p\text{ is prime}\}$, which is known to be not regular. The PL proof of this is standard and can be found in lots of places. One could show directly by a PL proof that in this case $L$ is not regular, though as Yuval has noted your proof doesn't quite do it.