¿Es regular si es regular?

Si es regular, ¿se deduce que es regular?$A^2$$A$

Mi intento de una prueba:

Sí, por contradicción, suponga que no es regular. A continuación, .A 2 = A ⋅ $A$$A^2 = A \cdot A$

Dado que la concatenación de dos idiomas no regulares no es regular, no puede ser regular. Esto contradice nuestra suposición. Entonces es regular. Entonces, si es regular, entonces es regular. A A 2$A^2$$A$$A^2$$A$

¿Es correcta la prueba?

¿Podemos generalizar esto a , , etc.? ¿Y también si es regular, entonces no necesita ser regular?A 4 A ∗$A^3$$A^4$$A^*$$A$

Ejemplo: no es regular pero es regular.A $A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$$A^*$

Considere el teorema de cuatro cuadrados de Lagrange . Establece que si luego . Si es regular, tome o tome . De cualquier manera, esto prueba la existencia de irregular de tal manera que es regular.B 4 = { 1 n | n ≥ 0 } B 2 A = B A = B 2 A A $B = \{1^{n^2}| n \geq 0\}$$B^4 = \{1^n | n \geq 0\}$$B^2$$A = B$$A = B^2$$A$$A^2$

Aquí hay un ejemplo de un lenguaje no computable tal que . Tome cualquier no computable (representada como un conjunto de números, por ejemplo, los códigos de las máquinas de Turing que se detienen) y defina Así contiene todas las palabras que no sean los de longitud para algunos . Si fuera computable, entonces podría calcular : dado , determine si (es decir, ceros) está en o no. Desde que asumimosA 2 = Σ ∗ K A = { w ∈ Σ ∗ : | w | ≠ 4 k  para todos los  k ∈ K } . A 4 k k ∈ K A K k 0 4 k 4 k A K $A$$A^2 = \Sigma^*$$K$

Reclamación: . Sea cualquier palabra de longitud . Si no es una potencia de , entonces y la palabra vacía está en , entonces . Si es una potencia de entonces no es una potencia de . Escriba , donde . Ambos entonces . w n n 4 w ∈ A A w ∈ A 2 n 4 n / 2 4 w = x y | x | = | y | = n / 2 x , y ∈ A w = x y ∈ A $A^2 = \Sigma^*$$w$$n$$n$$4$$w \in A$$A$$w \in A^2$$n$$4$$n/2$$4$$w = xy$$|x| = |y| = n/2$$x,y \in A$$w = xy \in A^2$

Su prueba aún da un gran salto (argumentando que la concatenación de idiomas no regulares no es regular).

$A=\{1^p: p\text{ is a prime}\}$$A^2=\{1^{2k}: k>1\}$

Esto no resuelve la pregunta por completo, pero proporciona una fuerte evidencia de que la respuesta es no (de lo contrario, la conjetura de Goldbach es falsa). Sin embargo, la respuesta puede ser muy difícil de probar, si este es el único ejemplo conocido.

El reclamo es incorrecto.

$D$$x \in D$$y\in D$$|y| > 4|x|$$|x|>4|y|$^$\dagger$

$A = \Sigma^* \setminus D$$A$

$A^2 = \Sigma^*$ $\ \ \ $

^$\dagger$_{$|y|>2|x|$$|y|>2|x|+2$$|y|>4|x|$}

$X \subseteq {1}^\ast$$A=\{1\} \cup \{1^{2x}:x \in \mathbb N\} \cup \{1^{2x+1}:1^x \in X\}$

$A$$A^2=1^{\ast}$

$U\subseteq \mathbb{N}$$I = \{2u+1\mid u\in U\}\cup\{0,2,4,\dots\}$$L = \{a^i\mid i\in I\}$$L$$L^2 = \{a^{2n}\mid n\in \mathbb{N}\} \cup \{a^n\mid n\geq \min\,I\}$

Otro ejemplo, de una pregunta que fue marcada como un duplicado de esto, es considerar el lenguaje no regular . Cualquier número par es la suma de y  , que son ambos compuestos; cualquier número impar es la suma de y  , que son ambos compuestos ( para algunos ). Por lo tanto, , que es regular porque es co-finito (es el complemento de ).$\{a^k\mid m\text{ is composite}\}$$n\geq 8$$n-4$$4$$n\geq 13$$n-9$$9$$n-9=2m$$m\geq 2$$A^2 = \{a^8,a^{10}\}\cup\{a^k\mid k\geq 12\}$$\{\epsilon,a,aa,\dots,a^6,a^7,a^9,a^{11}\}$