patternMinor
Is square numbers written in binary a regular language?
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!
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\}$.
$$
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.