Define a language S containing words over the alphabet = {a, b} inductively in the following way:

• The empty word is in S: S.

• If u, v S, then auavb S.

• If u, v, w S, then buavaw S.

1. (1p) Use recursion to define two functions #_a, #_b ^* that return the number of occurrences of a and b, respectively, in their input.

2. (2p) Use induction to prove that w S. #_a(w) = 2 #_b(w).

   Hint: You might want to show that #_a(auavb)=2+#_a(u)+#_a(v). How do you prove this? This property follows from a lemma that you can perhaps prove by induction: u,v^*.#_a(uv)=#_a(u)+#_a(v).