Whether $L=\{(a^m,a^n)\}^*$ is regular or not?

Question

I am condidering the automatic structure for Baumslag-Solitar semigroups. And I have a question. For any $m,n \in Z$, whether the set $L=\{(a^m,a^n)\}^*$ is regular or not. Here a set is regular means it can be recognized by a finite automaton.
Since the operations:union, intersection, complement, concatenation and Kleene star for the regular sets are closed (see here), I have tried to represent $L$ to be the result of some sets under the operations mentioned above. If it is successfully represented, $L$ will be regular. But I failed. So I want to ask for some clues for this question.
Thanks for your assistance.

Answer 1

As Boris has pointed out in the comments, so far your question doesn't make complete sense, because you haven't specified a finite alphabet $\Sigma$ such that $L\subseteq \Sigma^*$.

What I think you probably want is to consider $L$ as a language over $\Sigma = (A\cap\{\epsilon\})\times(A\cap\{\epsilon\})$, where we are simplifying strings over $\Sigma$ and writing them as pairs of strings over $A$, for example $(a,a)(a,\epsilon) = (a^2,a)$.

If this is what you mean, then for a given $m,n\in \mathbb{N}$, $L = \{(a^m,a^n)\}^*$ is indeed a regular language over $\Sigma$, which is obvious, since $(a^m,a^n)$ is just (the shorthand form of) a particular word over $\Sigma$, and so $(a^m,a^n)^*$ is a regular expression.

Answer 2

I am not sure to interpret your question correctly, so I shall give two different possible scenarios. Let $A = \{a\}$.

(1) Let $n, m \in \mathbf{N}$. Then $a^n$ and $a^m$ are words of $A^*$ and $(a^n, a^m)$ is an element of $A^* \times A^*$. Further $L = (a^n, a^m)^*$ is a subset of $A^* \times A^*$.

(2) Let $n, m \in \mathbf{Z}$. Then $a^n$ and $a^m$ are words of the free group $FG(A)$ and $(a^n, a^m)$ is an element of $FG(A) \times FG(A)$. Further $L = (a^n, a^m)^*$ is a subset of $FG(A) \times FG(A)$.

Now, the term regular leads to a frequent confusion in both settings and should be avoided, or at least used with great care. There are indeed two distinct notions, the rational and the recognizable subsets of a monoid $M$, which coincide in $A^*$ (thanks to Kleene theorem) but fail to coincide in $A^* \times A^*$ and $FG(A) \times FG(A)$.

For instance your language $L$ is always a rational subset, but $(a, a)^*$ is not recognizable. Further, the rational subsets of $A^* \times A^*$ are not closed under complement.

Just to be complete, let me remind these two definitions: the rational subsets of $M$ form the smallest class of subsets of $M$ containing the singletons and closed under finite union, product and star. By construction, rational sets are closed under finite union, product and star.

A subset $K$ of $M$ is recognizable if there is a finite monoid $F$ and a monoid morphism $f: M \to F$ such that $f^{-1}(f(K)) = K$. Recognizable sets are closed under finite union, finite intersection and complement, but are neither closed under product nor under star.

If $M$ is finitely generated, then every recognizable subset is rational, but there might be nonrecognizable sets that are rational, like in your example.