Programming language grammar
binary-tree, compiler-construction, grammar, parsing
Solution
Here are two hints:
Appending a 0 to a binary representation is equivalent to multiplication by 2.
Appending a binary representation to itself is equivalent to multiplication by 2^N + 1.
Problem
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 ```