1
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – xan May 3 '13 at 16:46
  • $\begingroup$ Proving that a subset of $L$ is irregular won't help, because there are many regular languages that contain irregular subsets. $\endgroup$ – MJD May 3 '13 at 16:47
  • $\begingroup$ 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? $\endgroup$ – xan May 3 '13 at 16:51
  • $\begingroup$ $L'$ is not equal to $10^*10^*1\cap L$, which contains 110001$ = 7^2$ and 100100001$= 17^2$. $\endgroup$ – MJD May 3 '13 at 16:57
  • $\begingroup$ Right, thank you. I write stupid things.. $\endgroup$ – xan May 3 '13 at 16:58

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.