String homomorphisms. If and are finite alphabets, define a string homomorphism to be a function : that has the property that for any u,v,(uv)=(u)(v). For example, the function :{0,,9,A,,F}{0,1} that converts a hexadecimal number with n0 digits into a binary number with 4n bits is a string homomorphism: ()(0)(A)(CAB)==0000=1010=110010101011 Intuitively, a string homomorphism does a "search and replace" where each symbol is replaced with a (possibly empty) string. Prove this more formally: that is, prove that if is a string homomorphism, then for any w=w1wn (where n0 and wj for 1jn ), we have (w)=(w1)(wn). Use induction on n. (a) State and prove the base case (n=0). (b) Assume that () is true for n=i and prove () for n=i+1. You may assume the following facts about strings: - For all x,x=x and x=x. - For all x,y,z, if xz=yz then x=y. - For all x,y,z, if xy=xz then y=z