12
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$ – Dave Clarke Feb 16 '13 at 8:09
  • $\begingroup$ @DaveClarke Edited the proof. $\endgroup$ – akshay Feb 16 '13 at 8:22
  • 3
    $\begingroup$ 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... ;-) $\endgroup$ – Andrej Bauer Feb 16 '13 at 8:49
  • 6
    $\begingroup$ @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. $\endgroup$ – Yuval Filmus Feb 16 '13 at 20:33
28
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I don't understand this proof; could you elaborate a little? $\endgroup$ – G. Bach Feb 16 '13 at 13:52
  • 2
    $\begingroup$ 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. $\endgroup$ – Shaull Feb 16 '13 at 14:10
  • 1
    $\begingroup$ Absolutely beautiful. $\endgroup$ – vonbrand Feb 16 '13 at 14:56
  • 3
    $\begingroup$ @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$. $\endgroup$ – Karolis Juodelė Feb 16 '13 at 20:04
  • 1
    $\begingroup$ @JonasKölker, agree. $\endgroup$ – Karolis Juodelė Feb 20 '14 at 15:23
8
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael♦ Feb 16 '13 at 22:08
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ What can we conclude about the question? $\endgroup$ – akshay Feb 16 '13 at 8:33
  • $\begingroup$ 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). $\endgroup$ – Shaull Feb 16 '13 at 8:36
  • 2
    $\begingroup$ In the presence of "real" proofs, I don't think using an unproven conjecture is fair. Maybe the connection is interesting for some? $\endgroup$ – Raphael♦ Feb 17 '13 at 9:56
  • $\begingroup$ 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). $\endgroup$ – Shaull Feb 17 '13 at 10:16
  • 1
    $\begingroup$ In fact if you use primes and semiprimes, you can use Chen's theorem. $\endgroup$ – sdcvvc Feb 17 '13 at 19:42
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ – Karolis Juodelė Feb 16 '13 at 20:19
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

Let $U\subseteq \mathbb{N}$ be any undecidable set, let $I = \{2u+1\mid u\in U\}\cup\{0,2,4,\dots\}$ and let $L = \{a^i\mid i\in I\}$. $L$ is undecidable so it certainly isn't regular. But $L^2 = \{a^{2n}\mid n\in \mathbb{N}\} \cup \{a^n\mid n\geq \min\,I\}$, which is regular because its complement is finite.

Improve this answer
$\endgroup$
0
$\begingroup$

Another example, from a question that was marked as a duplicate of this, is to consider the non-regular language $\{a^k\mid m\text{ is composite}\}$. Any even number $n\geq 8$ is the sum of $n-4$ and $4$, which are both composite; any odd number $n\geq 13$ is the sum of $n-9$ and $9$, which are both composite ($n-9=2m$ for some $m\geq 2$). Therefore, $A^2 = \{a^8,a^{10}\}\cup\{a^k\mid k\geq 12\}$, which is regular because it's co-finite (it's the complement of $\{\epsilon,a,aa,\dots,a^6,a^7,a^9,a^{11}\}$).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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