# Proving grammar only generate strings that is multiple of 3

Hello I have an exercise for homework and I was hopping to get some hints in order to solve it.

num-> 11 | 10 num' 01 | num 0 | num num

num'-> 00 num' | 1 num' | ε

I need to prove that my grammar produces only strings that is multiply of 3.

What i know is:

1. 11 is 3 so no problem there
2. adding 0 to the end of the num is irrelevant because it will be still dividable by 3.
3. same with num num
4. I know that is something about the 10 num' 01 pattern. (1001 is divided by 3)

I was thinking to try to prove it with sums (this is how i solve a previous exercise). However i am not sure that i can solve it that way.

• We get asked a lot how to prove that a grammar produces a particular question, so we wrote a reference question explaining how to approach such problems: cs.stackexchange.com/q/11315/755. It looks like the answers there show how to answer your question. Is there anything I'm missing that would make this not a duplicate of that question? – D.W. Nov 21 '15 at 7:11