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.

  • $\begingroup$ 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? $\endgroup$ – D.W. Nov 21 '15 at 7:11

Hint: num' generates (1) numbers of even length which are divisible by 3 and (2) numbers of odd length which equal 1 mod 3. For the rule num → 10 num' 01, consider the parity of the length of the number generated by num'.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.