# Proove this Grammer generates multiples of 3

1. Sep 4, 2013

### Kaffeine

1. Problem Statement
C ::= C 0 | A 1 | 0
A ::= B 0 | C 1 | 1
B ::= A 0 | B 1

Prove that the numbers generated are all multiples of 3.

3. The attempt at a solution

I have the solution, but am having trouble understanding it.
http://cm.bell-labs.com/who/ravi/teddy/solutions/XX0221.html [Broken]

Firstly, a question of semantics. They say that nonterminal "C" produces numbers of the form 3n. Doesnt this need to be proven somehow? Also, how do they reconcile the fact that in order to produce numbers of the form 3n, you must use the other nonterminals, doesn't this mean that we are no longer talking about nontermincal C, but about the grammer itself? This sounds like circular reasoning to me.

Also, their description of nontermincal C completely omits discussion of nonterminal B, isn't this problematic?

Finally, they do not integrate the 3 nonterminals of the grammer in any way, so I'm having trouble understanding how I can formally integrate the three cases potentially generating multiples of three into saying definetively that the grammer generates multiples of 3.

Please help me understand this a bit better, the theoretical side of Computer Science is confusing me quite a bit here.

Thank you!

Last edited by a moderator: May 6, 2017