Ist die Sprache der binären Darstellung perfekter Quadrate regelmäßig?

Lassen $\mbox{bin}(n)$ bezeichnen die binäre Darstellung einer ganzen Zahl $n$. Lassen$L = \{ \mbox{bin}(n^2) \mid n \in \mathbb{N} \}$.

Ist $L$ eine normale Sprache?

Ich denke, das kann man beweisen $L$ ist nicht regelmäßig mit dem Pump-Lemma, aber ich weiß nicht, wie ich es hier verwenden soll.

Wir beginnen mit einem Lemma.

Lemma. Lassen$a>b \geq 4$. Wenn$2^a+2^b+1$ ist dann ein Quadrat $a \geq 2b-3$.

Beweis. Lassen$2^a+2^b+1 = x^2$. Deutlich$x$ muss seltsam sein, sagen wir $x = 2y+1$. Dann$x^2 = 4y^2 + 4y + 1$, und so $(y+1)y = y^2+y = 2^{a-2} + 2^{b-2} = 2^{b-2}(2^{a-b}+1)$. Wenn$y$ ist auch dann noch $y+1$ ist seltsam und so $y = 2^{b-2}z$ für einige ungerade $z$, und deshalb $2^{a-b}+1 = (2^{b-2}z+1)z \geq 2^{b-2}+1$ und so $a \geq 2b-2$. Wenn$y$ ist dann zwangsläufig ungerade $y+1 = 2^{b-2}z$ für einige ungerade $z$, und deshalb $2^{a-b}+1 = z(2^{b-2}z-1) \geq 2^{b-2}-1 = 2^{b-3} + 1 + (2^{b-3}-2)$. Schon seit$b \geq 4$, können wir schließen, dass $a \geq 2b-3$. $\square$

Lassen $L' = L \cap 10^*10^*0001$. Nach dem Lemma sind alle Wörter in$L'$ sind von der Form $10^{a-b-1}10^{b-1}1$ mit $a-b-1 \geq (b-1)-3$. Darüber hinaus seit$2^{2c} + 2^{c+1} + 1 = (2^c+1)^2$, für alle $c \geq 3$, $10^{c-2}10^c1 \in L'$.

Wenn $L$ ist dann regelmäßig so ist $L'$, sagen wir, sein minimaler DFA hat $p$Zustände. Betrachten Sie das Wort$10^{p-2}10^p1 \in L'$und markieren Sie den Teilstring $0^p$. Das erweiterte Pump-Lemma zeigt das für einige$0 < q \leq p$, $10^{p-2}10^{p+q(t-1)}1 \in L'$ für alle $t \geq 0$. Nach unserem Lemma jedoch für alle$t$ Wir müssen haben $p-2 \geq p+q(t-1)-3$ und so $1 \geq q(t-1)$, was falsch ist für $t \geq 3$.