Programming language grammar

2
votes

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
1
parsingcompiler-constructionbinary-treegrammar
@DavidStratton: Eh? Induction is like basic maths technique, hardly a "showing off" word. If you're learning about compilers, you should know about induction already. It's kid of like complaining that "water" is a bragadoccio word. - Amadan
@Amadan - LOL Point taken. Comment removed. it was out of place anyway. I'm just so many years out of school that I have to think hard to remember terms I never use in day-to-day life. I'm just a geezer with failing memory is all. Bragadoccio - that's good. - David

1 Answers

10
votes

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.