# Is language of binary representations regular?

Let $bin(n)$ denote binary representation of an integer $n$. Let $L=\left\{bin(n^2):n\in\mathbb{N}\right\}$. Is $L$ a regular language?

• What is a "regular language"? – moray95 May 3 '13 at 16:22
• @moray95 Regular language – MJD May 3 '13 at 16:27

In general, if $p$ is any polynomial, then $\{ \operatorname{bin}(p(n)) : n\in\Bbb N \}$ is regular if and only if $p$ is constant or first degree.
It is easy to prove that this case, where $p$ is the second-degree polynomial $n^2$, is irregular, using the Myhill-Nerode theorem.
• It is very interesting what you say is in general. I didn't know that. Is it very hard to prove? I believe that in this particular case pumping lemma should be efficient (and that is only one way, I know, to prove such things) but completely don't know how to start. I was thinking maybe consider only particular subset of $L$ such as $10^{N-1}10^{N+1}1$ but this led me to nowhere. – xan May 3 '13 at 16:46
• Proving that a subset of $L$ is irregular won't help, because there are many regular languages that contain irregular subsets. – MJD May 3 '13 at 16:47
• You're right, thanks! But given subset of $L$ (let's call it $L'$) is equal to $10^*10^*1 \cap L$ so if $L$ is regular then $L'$ too. Then if I prove $L'$ not regular then $L$ not regular. Can this argument work? – xan May 3 '13 at 16:51
• $L'$ is not equal to $10^*10^*1\cap L$, which contains 110001$= 7^2$ and 100100001$= 17^2$. – MJD May 3 '13 at 16:57