é

Se $A^2$ é regular, segue-se que $A$ é regular?

Minha tentativa de prova:

Sim, por contradição, assuma que $A$ não é regular. Em seguida, $A^2 = A \cdot A$ .

Desde concatenação de duas línguas não regular não é regular $A^2$ não pode ser regular. Isso contradiz nossa suposição. Então $A$ é regular. Então, se $A^2$ é regular, então $A$ é regular.

A prova está correta?

Podemos generalizar isso para $A^3$ , $A^4$ , etc ...? E também se $A^*$ é regular, então $A$ não precisa ser regular?

Exemplo: $A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$ não é regular, mas $A^*$ é regular.

Considere o teorema dos quatro quadrados de Lagrange . Ele afirma que se então B 4 = { 1 n | n ≥ 0 } . Se B 2 for regular, faça A = B ou faça A = B 2 . De qualquer maneira, isso prova a existência de irregular A tal que A 2 é regular.$B = \{1^{n^2}| n \geq 0\}$$B^4 = \{1^n | n \geq 0\}$$B^2$$A = B$$A = B^2$$A$$A^2$

Aqui está um exemplo de uma linguagem não computável tal que A 2 = Σ ∗ . Pegue qualquer K não computável (representado como um conjunto de números, por exemplo, os códigos das máquinas de Turing que param) e defina A = { w ∈ Σ ∗ : | w | ≠ 4 k  para todos os  k ∈ K } . Então A contém todos os outros do que os de comprimento palavras 4 k por algum k ∈ K . Se $A$$A^2 = \Sigma^*$$K$

Reivindicação: . Seja w qualquer palavra de comprimento n . Se n não é uma potência de 4 , então w ∈ A e a palavra vazia estão em A , então w ∈ A 2 . Se n é uma potência de 4, então n / 2 não é uma potência de 4 . Escreva w = x y , onde | x | = | y | = n $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$ . Ambos então w = x y ∈ A 2 .$x,y \in A$$w = xy \in A^2$

Your proof still makes a huge jump (arguing that concatenation of non-regular languages is non-regular).

If the Goldbach conjecture is true, then the answer to the question is no: Consider the non-regular language $A=\{1^p: p\text{ is a prime}\}$. Then by the Goldbach conjecture, $A^2=\{1^{2k}: k>1\}$, which is regular.

This doesn't solve the question entirely, but it gives strong evidence that the answer is no (otherwise the Goldbach conjecture is false). However, the answer may be very hard to prove, if this is the only known example.

The claim is wrong.

Let $D$ be non-regular language which is "sparse": if $x \in D$ then any other $y\in D$ satisfies $|y| > 4|x|$ (or $|x|>4|y|$)^$\dagger$. It's not too difficult to see that many non-regular languages can be sparse.

Now define $A = \Sigma^* \setminus D$. From closure properties (complementation), $A$ must be non-regular.

However, $A^2 = \Sigma^*$ $\ \ \ $ (can you see why?)

^$\dagger$ _{I think $|y|>2|x|$ is enough, but may cause some nasty edge cases. $|y|>2|x|+2$ should be enough though, so let's take $|y|>4|x|$ to be on the safe side.}

Take any nonregular $X \subseteq {1}^\ast$ and define $A=\{1\} \cup \{1^{2x}:x \in \mathbb N\} \cup \{1^{2x+1}:1^x \in X\}$.

It is easy to see $A$ is nonregular, while $A^2=1^{\ast}$.

Let $U\subseteq \mathbb{N}$ be any undecidable set, let $I = \{2u+1\mid u\in U\}\cup\{0,2,4,\dots\}$ and let $L = \{a^i\mid i\in I\}$. $L$ is undecidable so it certainly isn't regular. But $L^2 = \{a^{2n}\mid n\in \mathbb{N}\} \cup \{a^n\mid n\geq \min\,I\}$, which is regular because its complement is finite.

Another example, from a question that was marked as a duplicate of this, is to consider the non-regular language $\{a^k\mid m\text{ is composite}\}$. Any even number $n\geq 8$ is the sum of $n-4$ and $4$, which are both composite; any odd number $n\geq 13$ is the sum of $n-9$ and $9$, which are both composite ($n-9=2m$ for some $m\geq 2$). Therefore, $A^2 = \{a^8,a^{10}\}\cup\{a^k\mid k\geq 12\}$, which is regular because it's co-finite (it's the complement of $\{\epsilon,a,aa,\dots,a^6,a^7,a^9,a^{11}\}$).