1

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?

xan
  • 2,053

1 Answers1

2

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.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • 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 03 '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 03 '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 03 '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 03 '13 at 16:57
  • Right, thank you. I write stupid things.. – xan May 03 '13 at 16:58
  • That's not stupid. It doesn't work, but it was worth considering. I think there are a lot of ways to solve this problem. – MJD May 03 '13 at 16:58