7
$\begingroup$

Let $\mbox{bin}(n)$ denote the binary representation of an integer $n$. Let $L = \{ \mbox{bin}(n^2) \mid n \in \mathbb{N} \}$.

Is $L$ a regular language?

I think one can prove that $L$ is not regular by using the pumping lemma, but I don't know how to use it here.

$\endgroup$
  • 4
    $\begingroup$ Welcome to CSTheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$ – David Eppstein May 3 '13 at 17:59
  • $\begingroup$ you may use :[wikipedia]en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages $\endgroup$ – Fayez Abdlrazaq Deab May 4 '13 at 8:34
  • 3
    $\begingroup$ An interesting question. While it seems that the language should not be regular, it should be noted that the language of binary representations of quadratic residues modulo power of 2 is regular. $\endgroup$ – Karolis Juodelė May 4 '13 at 15:23
  • 3
    $\begingroup$ math.stackexchange.com/questions/380411/… somebody already asked here the same, and includes tentative answer. $\endgroup$ – Alejandro Sazo May 5 '13 at 1:38
  • $\begingroup$ There are other methods to show that a language is not regular (see cs.stackexchange.com/questions/1031/…). I think I'd use Myhill–Nerode theorem. $\endgroup$ – AProgrammer May 5 '13 at 12:50
10
$\begingroup$

We start with a lemma.

Lemma. Let $a>b \geq 4$. If $2^a+2^b+1$ is a square then $a \geq 2b-3$.

Proof. Let $2^a+2^b+1 = x^2$. Clearly $x$ must be odd, say $x = 2y+1$. Then $x^2 = 4y^2 + 4y + 1$, and so $(y+1)y = y^2+y = 2^{a-2} + 2^{b-2} = 2^{b-2}(2^{a-b}+1)$. If $y$ is even then $y+1$ is odd and so $y = 2^{b-2}z$ for some odd $z$, and therefore $2^{a-b}+1 = (2^{b-2}z+1)z \geq 2^{b-2}+1$ and so $a \geq 2b-2$. If $y$ is odd then necessarily $y+1 = 2^{b-2}z$ for some odd $z$, and therefore $2^{a-b}+1 = z(2^{b-2}z-1) \geq 2^{b-2}-1 = 2^{b-3} + 1 + (2^{b-3}-2)$. Since $b \geq 4$, we can conclude that $a \geq 2b-3$. $\square$

Let $L' = L \cap 10^*10^*0001$. According to the lemma, all words in $L'$ are of the form $10^{a-b-1}10^{b-1}1$ with $a-b-1 \geq (b-1)-3$. Moreover, since $2^{2c} + 2^{c+1} + 1 = (2^c+1)^2$, for all $c \geq 3$, $10^{c-2}10^c1 \in L'$.

If $L$ is regular then so is $L'$, say its minimal DFA has $p$ states. Consider the word $10^{p-2}10^p1 \in L'$, and mark the substring $0^p$. The extended pumping lemma shows that for some $0 < q \leq p$, $10^{p-2}10^{p+q(t-1)}1 \in L'$ for all $t \geq 0$. However, according to our lemma, for all $t$ we must have $p-2 \geq p+q(t-1)-3$ and so $1 \geq q(t-1)$, which is false for $t \geq 3$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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