Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
The first proof make a huge jump. What is your proof that $A$ is not regular implies $A^2$ is not regular? Proving that properly might lead you to intuition to help answer the rest of the question, if indeed it is true. –  Dave Clarke Feb 16 '13 at 8:09
    
@DaveClarke Edited the proof. –  akshay Feb 16 '13 at 8:22
3  
How you manage to spell "Am i Correct?" that way is very intriguing. As a general advice: when hundreds of people read what you wrote, general decency demands that you pay attention to how you write... ;-) –  Andrej Bauer Feb 16 '13 at 8:49
4  
@AndrejBauer The OP could be someone who is not a native speaker of English, and who might not have yet had the opportunity of getting instruction on formal English. This is no reason to discourage anyone, though it could be helpful to correct them. –  Yuval Filmus Feb 16 '13 at 20:33
add comment

5 Answers 5

up vote 16 down vote accepted

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.

share|improve this answer
    
I don't understand this proof; could you elaborate a little? –  G. Bach Feb 16 '13 at 13:52
1  
Explaining this (beautiful) proof: We have that $B\notin REG$, and that $B^4\in REG$. Observe that $B^4=(B^2)^2$. Now, if $B^2\in REG$, then by taking $A=B$ we have a counterexample, and if $B^2\notin REG$ then by taking $A=B^2$ we have a counterexample. –  Shaull Feb 16 '13 at 14:10
1  
Absolutely beautiful. –  vonbrand Feb 16 '13 at 14:56
2  
@YuvalFilmus, indeed, but I didn't have a proof and I didn't want to leave any doubt. Now I seem to have found one. "A number $n$ is a sum of two squares if and only if all prime factors of the form $4k+3$ have even exponent in the prime factorization of $n$." Let $n$ be the pumping length. Consider $w = (n!)^2$. Let $p$ be a prime of the form $4k+3$ and let $m$ be the length we choose to pump. Then, $w + (p-1)\frac{w}{m}\cdot m = pw$ has an odd exponent on $p$ and is thus not in $B^2$. –  Karolis Juodelė Feb 16 '13 at 20:04
1  
@JonasKölker, agree. –  Karolis Juodelė Feb 20 at 15:23
show 4 more comments

Here is an example of a non-computable language $A$ such that $A^2 = \Sigma^*$. Take any non-computable $K$ (represented as a set of numbers, e.g. the codes of Turing machines that halt), and define $$ A = \{ w \in \Sigma^* : |w| \neq 4^k \text{ for all } k \in K \}. $$ So $A$ contains all words other than ones of length $4^k$ for some $k \in K$. If $A$ were computable then you could compute $K$: given $k$, determine whether $0^{4^k}$ (that is, $4^k$ zeroes) is in $A$ or not. Since we assumed $K$ is not computable, $A$ must also be non-computable.

Claim: $A^2 = \Sigma^*$. Let $w$ be any word of length $n$. If $n$ is not a power of $4$, then $w \in A$ and the empty word is in $A$, so $w \in A^2$. If $n$ is a power of $4$ then $n/2$ is not a power of $4$. Write $w = xy$, where $|x| = |y| = n/2$. Both $x,y \in A$ so $w = xy \in A^2$.

share|improve this answer
1  
For beginners, a proof sketch for "$A$ undecidable" may be in order. Also, a small hurdle may be that you use $K$ as a formal language and as a set of numbers (which is fair, assuming suitable semantics for $K$, but maybe unfamiliar). Otherwise, very nice idea. –  Raphael Feb 16 '13 at 22:08
add comment

Your proof still makes a huge jump (arguing that concatenation of non-regular languages is non-regular).

If the Goldbach conjecture is true, then the answer to the question is no: Consider the non-regular language $A=\{1^p: p\text{ is a prime}\}$. Then by the Goldbach conjecture, $A^2=\{1^{2k}: k>1\}$, which is regular.

This doesn't solve the question entirely, but it gives strong evidence that the answer is no (otherwise the Goldbach conjecture is false). However, the answer may be very hard to prove, if this is the only known example.

share|improve this answer
    
What can we conclude about the question? –  akshay Feb 16 '13 at 8:33
    
Assuming the Goldbach conjecture -if $A^2$ is regular, than $A$ may still be non-regular. So: proving that the answer is "yes" would mean that the Goldbach conjecture is false (unlikely). –  Shaull Feb 16 '13 at 8:36
1  
In the presence of "real" proofs, I don't think using an unproven conjecture is fair. Maybe the connection is interesting for some? –  Raphael Feb 17 '13 at 9:56
    
Indeed, after the following answers, this is redundant. However, you can see a nice mathematical development here: an answer based on a well known conjecture, then a related answer (using Lagrange's theorem), which is based on a similar idea (decomposing a number to a sum). –  Shaull Feb 17 '13 at 10:16
1  
In fact if you use primes and semiprimes, you can use Chen's theorem. –  sdcvvc Feb 17 '13 at 19:42
show 1 more comment

The claim is wrong.

Let $D$ be non-regular language which is "sparse": if $x \in D$ then any other $y\in D$ satisfies $|y| > 4|x|$ (or $|x|>4|y|$)$\dagger$. It's not too difficult to see that many non-regular languages can be sparse.

Now define $A = \Sigma^* \setminus D$. From closure properties (complementation), $A$ must be non-regular.

However, $A^2 = \Sigma^*$ $\ \ \ $ (can you see why?)

$\dagger$ I think $|y|>2|x|$ is enough, but may cause some nasty edge cases. $|y|>2|x|+2$ should be enough though, so let's take $|y|>4|x|$ to be on the safe side.

share|improve this answer
    
I like how this question is getting increasingly more trivial proofs. Your idea of sparseness could be further simplified to a requirement that $1 \in A$ and $1^k \notin A \implies 1^{k-1} \in A$. –  Karolis Juodelė Feb 16 '13 at 20:19
add comment

Take any nonregular $X \subseteq {1}^\ast$ and define $A=\{1\} \cup \{1^{2x}:x \in \mathbb N\} \cup \{1^{2x+1}:1^x \in X\}$.

It is easy to see $A$ is nonregular, while $A^2=1^{\ast}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.