I have the following languages over the alphabet {$0$, $1$}, where each number is given in its binary representation:
$A\:=\:\left\{number\:x\:is\:a\:multiple\:of\:3\right\}$
$B\:=\:\left\{x=x_1x_2.......x_n\left|\sum _{k=1}^n\left(-1\right)^kx_k\:is\:a\:multiple\:of\:3\:\right|\right\}$
$C\:=\:\left\{x=x_nx_{n-1}.......x_1\left|\sum _{k=1}^n\left(-1\right)^kx_k\:is\:a\:multiple\:of\:3\:\right|\right\}$
How would I prove that the above $3$ languages are equivalent?
Also, how can we explain the relationship between these languages and the standard multiple of $3$ DFA:
For $B$ and $C$, I know that when you sum the digits of a regular number then if the sum is divisible by $3$, so is the number itself. I assume the same is applied in binary. Since we get the same sum in reverse order, the languages should be equivalent. But with binary it does not seem that simple as if you reverse the binary number, then different digits will be raised to different powers, so I am not too sure. Also, I am not sure how then we can relate this back to $A$ which is a much more general statement.
I am also not sure how these languages relate with the $DFA$. I know the $DFA$ is largely constructed using the $mod$ $3$ operator but I don't know if that is something the $3$ languages also use.
I would appreciate any advice on how to do this!
"I assume the same is applied in binary": This is not the case (consider $3=(11)_2$ and $7=(111)_2$ for example).
Indeed, in binary it is the alternating sum of bits that determines whether the number is a multiple of $3$, just like testing divisibility by $11$ for regular decimal numbers. (And for the same reason, since $3=(11)_2$!)
I highly recommend finding a proof of the divisibility tests for $3$ and $11$ for regular decimal numbers and understanding them; then you will see why the alternating sum of bits is relevant here (and you will also avoid this pitfall in the future thanks to your deeper understanding).