Является ли регулярным , если

Если регулярно, следует ли из этого, что A регулярно?$A^2$$A$

Моя попытка доказательства:

Да, для противоречия предположим, что не является регулярным. Тогда 2 = ⋅ .$A$$A^2 = A \cdot A$

Поскольку конкатенация двух нерегулярных языков не является регулярной, не может быть регулярной. Это противоречит нашему предположению. Так что А регулярно. Так что, если A 2 регулярно, то A регулярно.$A^2$$A$$A^2$$A$

Является ли доказательство правильным?

Можем ли мы обобщить это на , A 4 и т. Д.? А также, если A ∗ регулярный, то A не должен быть регулярным?$A^3$$A^4$$A^*$$A$

Пример: не является регулярным, но A ∗ является регулярным.$A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$$A^*$

Рассмотрим теорему Лагранжа о четырех квадратах . В нем говорится, что если тогда B 4 = { 1 n | n ≥ 0 } . Если B 2 регулярно, возьмите A = B, иначе возьмите A = B 2 . В любом случае, это доказывает существование нерегулярного A такого, что A 2 является регулярным.$B = \{1^{n^2}| n \geq 0\}$$B^4 = \{1^n | n \geq 0\}$$B^2$$A = B$$A = B^2$$A$$A^2$

Вот пример такого невычислимого языка , что A 2 = Σ ∗ . Возьмем любой невычислимый K (представленный в виде набора чисел, например, кодов остановившихся машин Тьюринга) и определим A = { w ∈ Σ ∗ : | ш | ≠ 4 к  для всех  к ∈ K } . Так содержит все другое , чем те длины слова 4 к для некоторых к ∈ K . Если $A$$A^2 = \Sigma^*$$K$

Утверждение: . Пусть w - любое слово длины n . Если n не является степенью 4 , то w ∈ A и пустое слово находится в A , поэтому w ∈ A 2 . Если n является степенью 4, то n / 2 не является степенью 4 . Напишите w = x y , где | х | = | у | = н $A^2 = \Sigma^*$$w$$n$$n$$4$$w \in A$$A$$w \in A^2$$n$$4$$n/2$$4$$w = xy$ . Оба x , y ∈ A, поэтому w = x y ∈ A 2 .$|x| = |y| = n/2$$x,y \in A$$w = xy \in A^2$

Ваше доказательство все еще делает огромный скачок (утверждая, что объединение нерегулярных языков является нерегулярным).

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

Это не решает вопрос полностью, но дает убедительные доказательства того, что ответ отрицательный (в противном случае гипотеза Гольдбаха неверна). Тем не менее, ответ может быть очень трудно доказать, если это единственный известный пример.

Требование неверно.

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