Is the language of binary representation of perfect squares regular?
We start with a lemma.

Lemma. Let $a&gt;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 &lt; 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$.