Proove this Grammer generates multiples of 3

[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.

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

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!

 

[KataKoniK]

Thank you for bringing up these valid concerns. Let me try to address them one by one.

Firstly, the statement that nonterminal "C" produces numbers of the form 3n is based on the structure of the grammar itself. The grammar is designed in a way that every production rule will result in a number that is a multiple of 3. This can be proven by examining the production rules and the structure of the grammar. For instance, in the production rule C ::= C 0, we can see that the number produced by C is the same as the number produced by C 0, but with an extra 0 at the end. Since C 0 is already a multiple of 3 (according to our assumption), adding a 0 at the end will not change this fact. Similarly, in the production rule A ::= B 0, the number produced by A will be the number produced by B with an extra 0 at the end. Since B is also a nonterminal that produces multiples of 3, this will result in a number that is still a multiple of 3. This can be proven for all the production rules of the grammar, showing that all numbers produced by nonterminal C will be multiples of 3.

Secondly, the grammar itself is made up of three nonterminals (C, A, B) and a set of production rules that define how these nonterminals can be combined to generate numbers. Therefore, nonterminal C is not a separate entity from the grammar itself, but rather an integral part of it. The production rules for C do not need to mention nonterminal B explicitly because B is already covered by the production rules for A and C. For example, the production rule C ::= A 1 will ultimately result in the production rule A ::= B 0, which in turn will use the production rule B ::= A 0. Therefore, all cases of nonterminal B are accounted for in the grammar.

Lastly, the integration of the three nonterminals in the grammar is implicit in the production rules. As mentioned before, the production rules are designed in a way that every possible combination of nonterminals will result in a number that is a multiple of 3. This can be proven by tracing the production rules and examining the structure of the grammar. By doing so, we can see that every number produced by the grammar will be a multiple of 3.

I hope this helps in