A linguagem da representação binária de quadrados perfeitos é regular?

Vamos denotar a representação binária de um número inteiro . Deixe .$\mbox{bin}(n)$$n$$L = \{ \mbox{bin}(n^2) \mid n \in \mathbb{N} \}$

é uma linguagem comum?$L$

Acho que se pode provar que não é regular usando o lema de bombeamento, mas não sei como usá-lo aqui.$L$

Começamos com um lema.

Lema. Seja . Se é um quadrado, então .$a>b \geq 4$$2^a+2^b+1$$a \geq 2b-3$

Prova. Seja . Claramente deve ser ímpar, diga . Então , e assim . Se é par, então é ímpar e, portanto, para ímpar e, portanto, e então . Se é ímpar, então necessariamente para algum ímpar e, portanto,$2^a+2^b+1 = x^2$$x$$x = 2y+1$$x^2 = 4y^2 + 4y + 1$$(y+1)y = y^2+y = 2^{a-2} + 2^{b-2} = 2^{b-2}(2^{a-b}+1)$$y$$y+1$$y = 2^{b-2}z$$z$$2^{a-b}+1 = (2^{b-2}z+1)z \geq 2^{b-2}+1$$a \geq 2b-2$$y$$y+1 = 2^{b-2}z$$z$$2^{a-b}+1 = z(2^{b-2}z-1) \geq 2^{b-2}-1 = 2^{b-3} + 1 + (2^{b-3}-2)$. Desde , podemos concluir que . $b \geq 4$$a \geq 2b-3$$\square$

Seja . De acordo com o lema, todas as palavras em têm a forma com . Além disso, como , para todos os , .$L' = L \cap 10^*10^*0001$$L'$$10^{a-b-1}10^{b-1}1$$a-b-1 \geq (b-1)-3$$2^{2c} + 2^{c+1} + 1 = (2^c+1)^2$$c \geq 3$$10^{c-2}10^c1 \in L'$

Se é regular, então também é , digamos que seu DFA mínimo tenha estados. Considere a palavra e marque a substring . O lema de bombeamento estendido mostra que, para cerca de , para todos os . No entanto, de acordo com nosso lema, para todos os , devemos ter e, portanto, , o que é falso para .$L$$L'$$p$$10^{p-2}10^p1 \in L'$$0^p$$0 < q \leq p$$10^{p-2}10^{p+q(t-1)}1 \in L'$$t \geq 0$$t$$p-2 \geq p+q(t-1)-3$$1 \geq q(t-1)$$t \geq 3$