Apakah

Jika $A^2$ teratur, apakah itu mengikuti bahwa $A$ teratur?

Upaya saya pada bukti:

Ya, untuk kontradiksi anggaplah bahwa $A$ tidak teratur. Kemudian $A^2 = A \cdot A$ .

Karena penggabungan dua bahasa non-reguler adalah tidak biasa, $A^2$ tidak dapat teratur. Ini bertentangan dengan asumsi kami. Jadi $A$ biasa. Jadi jika $A^2$ teratur maka $A$ adalah reguler.

Apakah buktinya benar?

Bisakah kita menggeneralisasi ini menjadi $A^3$ , $A^4$ , dll ...? Dan juga jika $A^*$ biasa maka $A$ tidak perlu biasa?

Contoh: $A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$ tidak teratur tetapi $A^*$ teratur.

Pertimbangkan teorema empat persegi Lagrange . Ini menyatakan bahwa jika maka B 4 = { 1 n | n ≥ 0 } . Jika B 2 teratur, ambil A = B lain ambil A = B 2 . Either way, ini membuktikan keberadaan A yang tidak teratur sehingga A 2 teratur.$B = \{1^{n^2}| n \geq 0\}$$B^4 = \{1^n | n \geq 0\}$$B^2$$A = B$$A = B^2$$A$$A^2$

Berikut adalah contoh dari bahasa tidak dapat dihitung sehingga A 2 = Σ ∗ . Ambil K yang tidak dapat dihitung (direpresentasikan sebagai sekumpulan angka, mis. Kode mesin Turing yang berhenti), dan tentukan A = { w ∈ Σ ∗ : | w | ≠ 4 k  untuk semua  k ∈ K } . Jadi Sebuah berisi semua kata lain daripada yang panjang 4 k untuk beberapa k ∈ K . Jika $A$$A^2 = \Sigma^*$$K$

Klaim: . Biarkan w menjadi kata panjang n . Jika n bukan kekuatan 4 , maka w ∈ A dan kata kosongnya di A , jadi w ∈ A 2 . Jika n adalah kekuatan 4 maka n / 2 bukan kekuatan 4 . Tulis w = x y , di mana | 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$ . Keduanya x , y ∈ A jadi w = x y ∈ A 2 .$|x| = |y| = n/2$$x,y \in A$$w = xy \in A^2$

Bukti Anda masih membuat lompatan besar (dengan alasan bahwa rangkaian bahasa non-reguler adalah non-reguler).

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

Ini tidak menyelesaikan pertanyaan sepenuhnya, tetapi memberikan bukti kuat bahwa jawabannya adalah tidak (kalau tidak dugaan Goldbach salah). Namun, jawabannya mungkin sangat sulit untuk dibuktikan, jika ini adalah satu-satunya contoh yang diketahui.

Klaim itu salah.

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

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