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 ?

  • $\begingroup$ Sorry,as I could not write (a^(n+1)) ^(n-1) properly. $\endgroup$ Jan 2 '15 at 12:12
  • 2
    $\begingroup$ Exponential is syntactically right-associative. So $a^{m^n}$ is to be read $a^{(m^n)}$. Note that $(a^m)^n=a^{m\times n}$. - - - Then (a^(n+1)) ^(n-1) is to be written $(a^{n+1})^{n-1}$, which then prints as $(a^{n+1})^{n-1}$ (and is equal to $a^{n^2-1}$). - - - Maybe you can edit your question to improve notation. $\endgroup$
    – babou
    Jan 2 '15 at 12:42
  • $\begingroup$ @ babou :Thank you. Can you tell me whether my proof is right or wrong. $\endgroup$ Jan 2 '15 at 12:45
  • $\begingroup$ If it were to be read as $\left(a^m\right)^n=a^{mn}$, the constraint $m>n$ would not make much sense as multiplication is commutative. Then $m \neq n$ would suffice. $\endgroup$ Jan 2 '15 at 13:27
  • $\begingroup$ Your proof cannot be correct: if $|uv| \leq n$, $u$ cannot be longer than $n$. Furthermore, you don't know what $u, v, w$ are, you cannot just assume $u=\left(a^{n+1}\right)^{n-1}$ or $w=\epsilon$. $\endgroup$ Jan 2 '15 at 13:33

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.


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.

  • $\begingroup$ Just for example ,in the case $a^{m^n}$ take m = 8 and n = 1 , then it is regular. But if m = 2 and n = 3 , then also it is regular but it breaks the condition ( m>n). In fact for all n = 1 it is regular. $\endgroup$ Jan 2 '15 at 18:40
  • $\begingroup$ What do you mean by "then it is regular"? $a^{8^1}$ is a word, but "regular" is a property of languages, not individual words. You should instead say that $a^{8^1}$ is in the language. Also notice, as remarked above, that if you're reading the problem as $(a^m)^n$ then you lose most of the constraint $m>n$, since $(a^m)^n=a^{mn}=a^{nm}=(a^n)^m$. $\endgroup$ Jan 2 '15 at 19:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.