Let L be the language over sigma = {0, 1} consisting of all strings with an equal number of 0's and 1's. Let G be the grammar with the productions S rightarrow 0S1 | 1S0 | SS | epsilon. Clearly, every string in L(G) has an equal number of 0's and 1's, because the right side of every production has an equal number of 0's and 1's. The other direction is not so obvious. Prove by (strong) induction on the length of w that S rightarrow w if w L. Recall that A rightarrow u means that u can be derived from A in finitely many steps