¿Los números cuadrados escritos en binario son un lenguaje regular?

Tengo problemas para tratar de determinar si todos los números cuadrados (1, 4, 9, 16, ...) escritos en forma binaria (1, 100, 1001, ...) son un lenguaje regular.

Después de algunos intentos de encontrar un patrón común de esos números, descubrí que para cualquier número cuadrado $n^2$, $n^2 mod 4$o es igual a 0 o 1, por lo que puedo dibujar un gráfico DFA con 4 estados para reconocer este lenguaje. Pero aparentemente, el DFA que dibujé en realidad reconoce un superconjunto del lenguaje de números cuadrados en cuestión. Estoy atorado aqui.

¿Alguien podría darme algunas pistas sobre este problema? Si no es un idioma normal, ¿cómo debo probarlo?

También estoy muy interesado en saber cómo abordar este tipo de preguntas de la mejor manera en el futuro. Sé que en muchos casos, si tenemos la intuición de que los autómatas tienen que hacer un seguimiento de lo que ya se ha visto (como$a^i b^i$), entonces se necesitan estados indeterminados para que los autómatas calculen, por lo que no es finito ni regular. Entonces podemos usar el lema de bombeo para demostrar que no es regular. Sin embargo, no puedo decir si este idioma es regular todavía, así que realmente no tengo idea de qué hacer a continuación.

¡Gracias!

Aquí hay una solución de alta tecnología. Denotar su idioma por . Szalay mostró que Desde aquí es bastante fácil demostrar que no es regular, reduciéndolo a .$L$

Bueno, esta es la tercera vez que reescribo esta respuesta. El usuario Yuval Filmus señaló dos errores muy muy tontos que cometí en las dos versiones anteriores.

Bueno, finalmente encontré una solución simple al problema. Creo que funciona

Primero tenemos esas palabras de este tipo:

$1(00)^p1(00)^p001$

Son números cuadrados.

Prueba:

He buscado información sobre números cuadrados y luego he encontrado "números octogonales centrados", que son números formados por capas de múltiplos de ocho, pero no la primera capa. La primera capa es una, la segunda ocho, la tercera dieciséis y así sucesivamente.

Entonces cada capa tiene un "ocho" más que la anterior. El número de ochos en un número octogonal centrado se puede calcular usando la fórmula de Gauss:

$\frac{n^2 + n}{2}$

Luego multiplicamos por ocho y agregamos uno, esto se debe a que la primera capa es solo un punto.

$\frac{8(n^2 + n)}{2}+1$

Simplementefying:

$4(n^2 + n) + 1$

Esa fórmula nos da los números cuadrados impares para cada n.

Voy a calcular la fórmula para el número cuatro y todas las potencias de cuatro.

Primero cuadramos el número, esto simplemente duplica los ceros del número. Luego agregamos el número al producto. Esto pone un "uno" en la posición comenzando desde la derecha. es la longitud de la palabra binaria.$\lceil|n|/2\rceil$$|n|$

En este momento tenemos palabras de esta forma:

$1(00)^p1(00)^p0$

Multiplicamos por cuatro, esto simplemente agrega dos ceros al final del número. Finalmente sumamos uno. Hemos terminado.

Bombeo

Puse .$i=0$

Primero el caso fácil

Si dejamos vacío, tomamos el número uno y uno o más ceros. Esto nos da palabras con el peso de hamming dos (el número de unos es dos). Solo hay un número desigual con el peso dos de Hamming, el número nueve (el único número cuadrado impar de la forma 2n + 1 es 9, lo vi en wikipedia: ver aquí ). Como todos los números que estamos bombeando son mayores que nueve, probamos este caso.$x$

Estuche duro

Dejamos el primer "uno" en su lugar y sacamos solo ceros. Podemos sacar hasta ceros.$p-1$

La palabra se verá así:

$10(00)^m1(00)^n001$ .

Donde y son números enteros más grande o igual a uno y$m$$n$$n > m$

Primero creeré que el número obtenido es un cuadrado, luego mostraré que es falso:

Como sabemos que todos los números cuadrados impares podemos obtenerlos con esta fórmula:

$4(n^2 + n) + 1$

Comenzamos a descomponer el número, restamos uno, este simple establece el último en cero y luego, dividimos entre cuatro, esto elimina dos ceros al final de la palabra binaria.

Entonces tendremos palabras como esta:

$10(00)^m1(00)^n0$, $n$y son números enteros más grande o igual a uno y . Estas palabras son un prefijo de la palabra completa.$m$$n > m$

Como creemos que esta cadena es parte de un número cuadrado, la palabra tuvo que formarse haciendo esta fórmula:

$(n^2 + n)$

$n$ no puede ser par

Volveremos a ver esta fórmula:

$n^2 + n$

Dado que creemos que las palabras que hemos bombeado son números cuadrados. Llamamos a las palabras que hemos bombeado tenemos eso:$m$

$m = n^2 + n$

Además, tenemos que puede representarse como la suma de dos números binarios, y , cada uno de ellos es una potencia de dos. Y tenemos que y$m$$m_1$$m_2$$\sqrt{m_1} < m_2$$m_1 > m_2$

Lo primero que notamos es que tiene que ser menor que . Esto se debe a que es más grande que la raíz cuadrada de , si era igual a , entonces será más grande que .$n$$m_2$$m_2$$m_1$$n$$m_2$$n^2$$m$

Ahora, cuando elevamos al cuadrado un número binario par, tenemos que el número al cuadrado tiene "más ceros" a la derecha del primer "uno" que el número original. Entonces "el más a la derecha" dentro de está a la izquierda del "más a la derecha" dentro de . Si agregamos a , tenemos que el "más a la derecha" dentro de es el "más a la derecha" en . Como es menor que . Tenemos que el "más a la derecha" dentro de está a la derecha del "más a la derecha" en . Por lo tanto, . Pero como dijimos eso$n^2$$n$$n$$n^2$$n^2 + n$$n$$n$$m_2$$n^2 + n$$m$$m \neq n^2 +n$$n^2 + n = m$ hemos llegado a una contradicción y por lo tanto $n$ no puede ser parejo

$n$ no puede ser desigual

De nuevo, tenemos eso $m$ es un número hecho agregando $n$ a $n^2$, entonces $m = n^2 + n$

Entonces notamos que $(n + 1)^2 - (n + 1) = n^2 + n$; Esto es porque:

$(n + 1)^2 - (n + 1) = n^2 + 2n + 1 -n -1$;

Y entonces:

$(n + 1)^2 - (n + 1) = n^2 + n$.

Otra forma de ver esto, es imaginar $n^2$ como un cuadrado con lados de longitud $n$. Este cuadrado está formado por cuadrados más pequeños de tamaño uno. Entonces, cuando agregamos$n$ cuadrados de tamaño uno al cuadrado anterior, el cuadrado anterior ahora es un rectángulo cuyos lados son $n$ y $n+1$. Ahora podemos imaginar$(n + 1)^2$ como otro cuadrado con lados de longitud $n + 1$. Este cuadrado también está formado por cuadrados más pequeños de tamaño uno. Si quitamos$n + 1$ cuadrados, tenemos un rectángulo de lados $n$ y $n+1$.

Tenemos eso $n + 1$ es un número par y la prueba sigue igual que antes para todos los números impares $n$ menos que $m_2 - 1$

Nuevamente, cuando elevamos al cuadrado un número binario par, tenemos que el número tiene "más ceros" a la derecha del primer "uno" que el número original. Entonces "el más correcto" dentro$(n + 1)^2$ está a la izquierda del "más a la derecha" dentro $n + 1$. Si restamos$n + 1$ a $(n + 1)^2$, tenemos que el "más a la derecha" dentro $n^2 + n$ es el "más a la derecha" en $n + 1$. Ya que$n + 1$ es más pequeño que $m_2$. Tenemos que el "más correcto" dentro$n^2 + n$ está a la derecha del "más a la derecha" en $m$.

Si $n = m_2 - 1$.

De nuevo, tenemos eso $n^2 + n = (n + 1)^2 - (n + 1)$. Ya que$m_2^2$ ($m_2$al cuadrado) es un número que es una potencia de dos, tiene un solo "uno" inicial y luego ceros. Cuando restamos$m_2$ a $m_2^2$, estamos girando todos los ceros a la izquierda del dígito más a la izquierda de $m_2$ dentro $m_2^2$ en "unos" y el número resultante no es como las palabras que estamos bombeando, debería haber al menos un "cero de separación" entre los unos.

Por lo tanto $m \neq n^2 +n$. Pero como dijimos eso$n^2 + n = m$ hemos llegado a una contradicción y por lo tanto $n$ No puede ser desigual.

Como $n$ no puede ser uniforme o desigual, tenemos que $n$no existe como un entero. Por lo tanto, las palabras que bombeamos no son el producto de la fórmula para números cuadrados impares. Como todas las palabras que estamos bombeando son impares, no pueden ser números cuadrados.