Let L = {x (a + b)^* | #_a(x) = #_b(x)}

1. Show that if x L and x begins and ends with the same symbol, then x = yz for some nonempty strings y, z L. (Hint. For x = x1 . . . xn, x1, . . . , xn {a, b}, define the function f : {0, . . . , n} Z by letting f(i) = #_a(x1 . . . xi) #_b(x1 . . . xi), and argue that y and z exist.)

2. Use (1) to find a CFG generating L in which S is the only nonterminal.