I'm struggling with the grammar that generates all binary numbers divisible by 3
I know that for a binary number to be divisible by 3 the sum of 1s in even bits mines the sum of 1s in odd bits must be divisible by 3.
After some googling, I found that you can do the dfa of it then convert it to cfg and you can get:
\begin{align*}
S &\to 0S \mid 1A \mid \epsilon \\
A &\to 0B \mid 1S \\
B &\to 1B \mid 0A
\end{align*}
I am surprised that this homework takes place before the lectures for finite automata, So, I have no idea how to get this grammar, may anyone explain.
UPDATE:
Thanks to Brain, motivated by his idea I've come to the following grammar which basically almost the same to the one I posted above:
The Idea is if a binary number concatenated by a 0 to the right the result is the number multiplied by 2 if it concatenated by 1 the result is the number multiplied by 2 plus 1
Eg:
$$
W = 10 = (2)_{10}, \text{ then } W0 = 100 = (4)_{10} \\
W = 10 = (2)_{10}, \text{ then } W1 = 101 = (5)_{10}
$$
by this logic we can denote the following states:
$$
S: \text{ binary numbers divisible by 3 with rest 0 } \\
A: \text{ binary numbers divisible by 3 with rest 1 } \\
B: \text{ binary numbers divisible by 3 with rest 2}
$$
therefore:
$
S: W = 3k, \text{ } W0 = 3k\text{(Go to S)},\text{ } W1 = 3k + 1\text{(Go to A)} \\
A: W = 3k + 1,\text{ } W0 = 3k + 2\text{(Go to B)},\text{ } W1 = 3k \text{(Go to S)} \\
B: W = 3k + 2,\text{ } W0 = 3k + 1\text{(Go to A)},\text{ } W1 = 3k + 2 \text{(Go to B)} \\
$
Hence, the following grammar:
\begin{align*}
S &\to S0 \mid A1 \mid \epsilon \\
A &\to B0 \mid S1 \\
B &\to A0 \mid B1
\end{align*}
Best Answer
Here is one way to approach the problem of designing such a grammar without reference to automata. Imagine building the number from right to left, one bit at a time. At each stage we are about to write a bit in an even position or an odd position, and $s_{\text{even}}-s_{\text{odd}}$ is congruent to $0,1$, or $2$ modulo $3$, where $s_{\text{even}}$ is the number of $1$ bits in even positions so far, and $s_{\text{odd}}$ is the number of $1$ bits in odd positions so far. (I am numbering the positions from the right.) Thus, at each stage of generating a bit string we are in one of $2\cdot 3=6$ possible states, and I’ll assign a nonterminal to each of them as follows:
Now it’s quite easy to come up with the needed productions. At the beginning we’re in state $S$, about to write a bit in an odd position when $s_{\text{even}}-s_{\text{odd}}\equiv0\pmod3$. If we write a $0$, $s_{\text{even}}-s_{\text{odd}}$ doesn’t change, but we’ll be writing a the next bit in an even position, so we want to be in state $A$; this means that there should be a transition $S\to A0$. If instead we write a $1$, $s_{\text{odd}}$ increases by $1$, so that we now have $s_{\text{even}}-s_{\text{odd}}\equiv2\pmod3$, and we’ll be writing the next bit in an even position, so we want to be in state $E$; thus, there should be a transition $S\to E1$. Finally, because at the moment $s_{\text{even}}-s_{\text{odd}}\equiv0\pmod3$, we do currently have a multiple of $3$, so we want to be able to stop here; we arrange that by having a transition $S\to\epsilon$.
If we carry out the same kind of analysis for each of the other five nonterminals, we get the following productions:
$$\begin{align*} &S\to A0\mid E1\mid\epsilon\\ &A\to S0\mid D1\mid\epsilon\\ &B\to C0\mid A1\\ &C\to B0\mid S1\\ &D\to E0\mid C1\\ &E\to D0\mid B1 \end{align*}$$
These do allow the empty word to be generated (via $S\Rightarrow\epsilon$); if this is not wanted, it can be eliminated by adding a nonterminal $X$ with productions $X\to A0\mid E1\mid\epsilon$, eliminating the production $S\to\epsilon$, and replacing the productions $A\to S0$ and $C\to S1$ by $A\to X0$ and $C\to X1$, respectively.
Clearly the resulting grammar is not has more nonterminals and more productions that are actually necessary, but I think that its construction and operation are relatively straightforward.