Exercise 2.21, Programming Languages book by Ravi Sethi

The following grammar generates numbers in binary notation:

a. The generated numbers are all multiples of 3.

We prove by induction on the length s of the generated string that, for n >= 0, nonterminal C generates numbers of the form 3n; A generates numbers of the form 3n+1; and B generates numbers of the form 3n+2.

The basis, s <= 2 is by enumeration. C generates 0, 00, and 11, the representations of 0, 0, and 3, respectively, all multiples of 3. A generates 1 and 01, and 1 is of the form 3n+1. B generates 10, the representation of 2, which is of the form 3n+2.

For the inductive step, consider strings of length s.

Case. The first production is for nonterminal C. If the string ends in 0, it must be generated starting with production C ::= C 0. The suffix 0 corresponds to multiplication by 2. Since the C on the right side generates multiples of 3 by the inductive hypothesis, then so must C on the left. If the string ends in 1, it must be generated starting with production C ::= A 1. By the inductive hypothesis A generates a string representing 3n+1, so C represents 2(3n+1)+1, which equals 6n+3, a multiple of 3.

The cases for the strings generated by B and C are similar.

b. All multiples of 3 are generated by the grammar

We prove by induction on n >= 0 that all numbers of the form 3n are generated by C, numbers of the form 3n+1 are generated by A, and numbers of the form 3n+2 are generated by B.

The basis n <= 1 is by enumeration.

Inductive step. Suppose true for all smaller values, and consider n+1.

If n+1 is even, let it be 2m. Note that the inductive hypothesis applies to m, since m < n for n >= 2.

Then, 3(n+1) = 3(2m) = 2(3m). By the inductive hypothesis, C generates 3m, so by C ::= C 0, it also generates 2(3m). And, 3(n+1)+1 = 3(2m)+1 = 2(3m)+1, so A generates this by A ::= C 1 and the inductive hypothesis. And, 3(n+1)+2 = 3(2m)+2 = 2(3m)+2 = 2(3m+1), so B generates this by B ::= A 0.

If n+1 is odd, let it be 2m+1. Again, the inductive hypothesis applies to m since m < n for n >= 2.

Now, 3(2m+1) = 2(3m)+3 = 2(3m+1)+1, which C generates by rule C ::= A 1. And, 3(2m+1)+1 = 3(2m)+4 = 2(3m+2), which A generates by rule A ::= B 0. And, 3(2m+1)+2 = 3(2m)+5 = 2(3m+2)+1, which B generates by rule B ::= B 1.