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.) Use this to find a CFG generating L in which S is the only nonterminal.