HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is square numbers written in binary a regular language?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
writtennumbersregularlanguagebinarysquare

Problem

I'm having problem trying to determine if all square numbers (1, 4, 9, 16, ...) written in binary form (1, 100, 1001, ...) is a regular language.

After some attempts to find a common pattern of those numbers, I found out that for any square number $n^2$, $n^2 mod 4$ either equals to 0 or 1, and so I am able to draw a DFA graph with 4 states to recognize this language. But apparently, the DFA I drew actually recognizes a superset of the square number language in question. I'm stuck here.

Anyone could give me some clues on this problem? If it's not a regular language, how should I prove it?

I am also very interested to know how I should approach to this kind of question the best way in the future. I know that in many cases, if we have the intuition that the automata has to keep a track of what is has seen already (like $a^i b^i$), then there's an undetermined states needed for the automata to compute, thus it's not finite or regular. We can then use Pumping lemma to prove it's not regular. However, I can't tell if this language is regular yet, so I don't really have an idea what to do next.

Thanks!

Solution

Here is a high-tech solution. Denote your language by $L$. Szalay showed that
$$
L \cap 10^10^1 = \{ 10^n10^{n+2}1 : n \geq 0 \} \cup \{110001, 1000010001\}.
$$
From here it's pretty easy to show that $L$ is not regular, by reduction to $\{a^nb^n : n \geq 0\}$.

Context

StackExchange Computer Science Q#84050, answer score: 9

Revisions (0)

No revisions yet.