patternMajor
Is $A$ regular if $A^{2}$ is regular?
Viewed 0 times
regularstackoverflowprogramming
Problem
If $A^2$ is regular, does it follow that $A$ is regular?
My attempt on a proof:
Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$.
Since concatenation of two non-regular language is not regular $A^2$ cannot be regular. This contradicts our assumption. So $A$ is regular. So if $A^2$ is regular then $A$ is regular.
Is the proof correct?
Can we generalize this to $A^3$, $A^4$, etc...? And also if $A^*$ is regular then $A$ need not be regular?
Example: $A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$ is not regular but $A^*$ is regular.
My attempt on a proof:
Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$.
Since concatenation of two non-regular language is not regular $A^2$ cannot be regular. This contradicts our assumption. So $A$ is regular. So if $A^2$ is regular then $A$ is regular.
Is the proof correct?
Can we generalize this to $A^3$, $A^4$, etc...? And also if $A^*$ is regular then $A$ need not be regular?
Example: $A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$ is not regular but $A^*$ is regular.
Solution
Consider Lagrange's four square theorem. It states that if $B = \{1^{n^2}| n \geq 0\}$ then $B^4 = \{1^n | n \geq 0\}$. If $B^2$ is regular, take $A = B$ else take $A = B^2$. Either way, this proves the existence of irregular $A$ such that $A^2$ is regular.
Context
StackExchange Computer Science Q#9829, answer score: 28
Revisions (0)
No revisions yet.