[Solved]: Is $A$ regular if $A^{2}$ is regular?

Problem Detail: 

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.

Asked By : akshay

Answered By : Karolis Juodelė

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9829