Answers to Problem 6.12 on page 193.

Both grammars generate the language of balanced parentheses.

In order to do the proof, it helps to number the productions.

For grammar G_a:

(a.1) S --> SS

(a.2) S --> (S)

(a.3) S --> Lambda

For grammar G_b:

(b.1) S --> S(S)

(b.2) S --> Lambda

Theorem 1: If w is any string generated by grammar G_b, then w is generated by grammar G_a.

Proof: By strong induction. We assume that the theorem holds for all strings of length less than w.

Consider any derivation of w by grammar G_b. Consider the first production in that derivation.

Case I: that first production is (b.1), namely S => S(S). Then w = u(v) where those parentheses are the ones generated in the first production. It follows that S =>* u and S=>* v also, which means that u and v are generated by G_b. By the inductive hypothesis, u and v are also generate by G_a. If alpha is the leftmost derivation of u by G_a and beta is the leftmost derivation of v by G_a, then (a.1)alpha(a.2)beta is a leftmost derivation of w by G_a.

Case II: that first production is (b.2). Then w = Lambda, which is generated by G_a by using (a.3).

This concludes the proof of Theorem 1.

Theorem 2: If w is any string generated by grammar G_a, then w is generated by grammar G_b.

Proof: By strong induction. We assume that the theorem holds for all strings of length less than w.

Consider any derivation of w by grammar G_a. Consider the first production in that derivation.

Case I: that first production is (a.1).

THIS PROOF IS UNFINISHED Case III: that first production is (a.3). Then w = Lambda, which is generated by G_a by using (b.2).