Si $L=\{(a^m,a^n)\}^*$ ¿es regular o no?

Question

Estoy considerando la estructura automática para los semigrupos Baumslag-Solitar. Y tengo una pregunta. Para cualquier $m,n \in Z$ si el conjunto $L=\{(a^m,a^n)\}^*$ es regular o no. Aquí un conjunto es regular significa que puede ser reconocido por un autómata finito.
Dado que las operaciones:unión, intersección, complemento, concatenación y estrella de Kleene para los conjuntos regulares son cerradas (véase aquí ), he tratado de representar $L$ para ser el resultado de algunos conjuntos bajo las operaciones mencionadas anteriormente. Si se representa con éxito, $L$ será regular. Pero he fallado. Así que quiero pedir algunas pistas para esta pregunta.
Gracias por su ayuda.

Answer 1

No estoy seguro de interpretar correctamente su pregunta, así que voy a plantear dos posibles escenarios diferentes. Dejemos que $A = \{a\}$ .

(1) Que $n, m \in \mathbf{N}$ . Entonces $a^n$ y $a^m$ son palabras de $A^*$ y $(a^n, a^m)$ es un elemento de $A^* \times A^*$ . Más información: $L = (a^n, a^m)^*$ es un subconjunto de $A^* \times A^*$ .

(2) Que $n, m \in \mathbf{Z}$ . Entonces $a^n$ y $a^m$ son palabras del grupo libre $FG(A)$ y $(a^n, a^m)$ es un elemento de $FG(A) \times FG(A)$ . Más información: $L = (a^n, a^m)^*$ es un subconjunto de $FG(A) \times FG(A)$ .

Ahora, el término regular lleva a una frecuente confusión en ambos escenarios y debería evitarse, o al menos utilizarse con mucho cuidado. En efecto, existen dos nociones distintas, la racional et le reconocible subconjuntos de un monoide $M$ que coinciden en $A^*$ (gracias al teorema de Kleene) pero no coinciden en $A^* \times A^*$ y $FG(A) \times FG(A)$ .

Por ejemplo, su idioma $L$ es siempre un subconjunto racional, pero $(a, a)^*$ no es reconocible. Además, los subconjuntos racionales de $A^* \times A^*$ son no cerrado bajo complemento.

Para completar, permítanme recordar estas dos definiciones: el racional subconjuntos de $M$ forman la clase más pequeña de subconjuntos de $M$ que contenga los monotonos y que esté cerrada bajo unión, producto y estrella finitos. Por construcción, los conjuntos racionales son cerrados bajo unión finita, producto y estrella.

Un subconjunto $K$ de $M$ est reconocible si existe un monoide finito $F$ y un morfismo monoide $f: M \to F$ tal que $f^{-1}(f(K)) = K$ . Los conjuntos reconocibles son cerrados bajo unión finita, intersección finita y complemento, pero no son cerrados bajo producto ni bajo estrella.

Si $M$ se genera finitamente, entonces todo subconjunto reconocible es racional, pero puede haber conjuntos no reconocibles que sean racionales, como en tu ejemplo.

Answer 2

Como ha señalado Boris en los comentarios, hasta ahora tu pregunta no tiene un sentido completo, porque no has especificado un finito alfabeto $\Sigma$ tal que $L\subseteq \Sigma^*$ .

Lo que creo que probablemente quieres es considerar $L$ como lengua sobre $\Sigma = (A\cap\{\epsilon\})\times(A\cap\{\epsilon\})$ donde estamos simplificando las cadenas sobre $\Sigma$ y escribirlos como pares de cadenas sobre $A$ por ejemplo $(a,a)(a,\epsilon) = (a^2,a)$ .

Si esto es lo que quieres decir, entonces para un determinado $m,n\in \mathbb{N}$ , $L = \{(a^m,a^n)\}^*$ es de hecho un lenguaje regular sobre $\Sigma$ lo cual es obvio, ya que $(a^m,a^n)$ es sólo (la forma abreviada de) una palabra particular sobre $\Sigma$ y así $(a^m,a^n)^*$ es una expresión regular.