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.

• Question: 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).