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:
- 11 is 3 so no problem there
- adding 0 to the end of the num is irrelevant because it will be still dividable by 3.
- same with num num
- 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.