Please answer problem 3 parts a and b as thoroughly as possible. Thank you for your time. This is theory of computation.

For any two strings x and y (Let's call this ST1) reverse(xy) reverse(y) reverse(x) For any collection of strings zi, z2, zn reve reverse (zn) reverse(zn-1) reverse(z1). (Call this ST2) ST3: For any string x, length(x) length (reverse(x). ST4: Assume that x and y are, in fact, the same string (i.e., xay). Then we have length (x) length(y). Assuming that x xn and y yiy2...yn, then for all i where 1 Sisj n, we also have x yi...y 3. Using STl, ST2, ST3, ST4 (when appropriate), prove the following: a) If x is a Palindrome, then so is x" for all n (n 200. (2 points) b) If z is a Palindrome for some n (n 0), the z itself is a Palindrome. (4 points) NOTE: Be careful with the n? 0 and n >0 issues