Programming language grammar

Question

I have this question in a Compilers coursework but I don't really know how to approach it. Could anyone please give me a better hint than what was given in the rubric?

Show that all binary strings generated by the following grammar have values divisible by 3.

Hint: use induction on the numerical values for nodes in the parse tree.

num -> 11 | 1001 | num 0 | num num

Answer 1

Here are two hints:

1. Appending a 0 to a binary representation is equivalent to multiplication by 2.

2. Appending a binary representation to itself is equivalent to multiplication by 2^N + 1.