est

Si est régulier, cela signifie-t-il que est régulier?$A^2$$A$

Ma tentative de preuve:

Oui, car la contradiction suppose que n'est pas régulier. Ensuite .$A$$A^2 = A \cdot A$

Comme la concaténation de deux langues non régulières n'est pas régulière, ne peut pas être régulier. Cela contredit notre hypothèse. Donc, est régulier. Donc, si est régulier, est régulier.$A^2$$A$$A^2$$A$

La preuve est-elle correcte?

Pouvons-nous généraliser cela à , , etc ...? Et aussi si est régulier alors n'a pas besoin d'être régulier?$A^3$$A^4$$A^*$$A$

Exemple: n'est pas régulier mais est régulier.$A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$$A^*$

Prenons le théorème des quatre carrés de Lagrange . Il indique que si puis . Si est régulier, prenez sinon prenez . Quoi qu'il en soit, cela prouve l'existence d'un irrégulier tel que est régulier.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$

Voici un exemple de langage non calculable tel que . Prenez n'importe quel non calculable (représenté comme un ensemble de nombres, par exemple les codes des machines de Turing qui s'arrêtent), et définissez Donc contient tous les mots autres que ceux de longueur pour un certain . Si était calculable, vous pourriez calculer : étant donné , déterminez si (c'est-à-dire zéros) est dans ou non. Puisque nous avons supposéA 2 = Σ ∗ K A = { w ∈ Σ ∗ : | w | ≠ 4 k  pour tous les  k ∈ K } . A 4 k k ∈ K A K k 0 4 k 4 k A K $A$$A^2 = \Sigma^*$$K$

Revendication: . Soit n'importe quel mot de longueur . Si n'est pas une puissance de , alors et le mot vide est dans , donc . Si est une puissance de alors n'est pas une puissance de . Écrivez , où . Les deux donc . 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$

Votre preuve fait encore un énorme bond (en faisant valoir que la concaténation des langues non régulières n'est pas régulière).

Si la conjecture de Goldbach est vraie, alors la réponse à la question est non: considérons le langage non régulier . Ensuite par la conjecture de Goldbach, A 2 = { 1 2 k : k > 1 } , qui est régulier.$A=\{1^p: p\text{ is a prime}\}$$A^2=\{1^{2k}: k>1\}$

Cela ne résout pas entièrement la question, mais cela donne des preuves solides que la réponse est non (sinon la conjecture de Goldbach est fausse). Cependant, la réponse peut être très difficile à prouver, si c'est le seul exemple connu.

La réclamation est fausse.

$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\}$

Un autre exemple, à partir d'une question qui a été marquée comme doublon, est de considérer la langue non régulière . Tout nombre pair est la somme de et  , qui sont tous deux composites; tout nombre impair est la somme de et  , qui sont tous deux composites ( pour certains ). Par conséquent, , qui est régulier parce qu'il est co-fini (c'est le complément 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}\}$