Use a structural induction proof to solve this question.

[ 3 ] (14 pts.) Palindromes! Consider the set PAL := {r e {a, b}* : x = rev(x)} , where rev(r) denotes the reverse of string r. For example, abba, aba, bb, a E PAL, but ab, bba, baba @ PAL. We can define a set S recursively as follows. A string s E S if 0. s = e, a, b, or 1. s = asja or s = bib where s e S. The goal of this problem and the next will be to prove that this recursive set S is a subset of PAL. We could show the other direction of containment using induction as well, but we'll leave that for another time (or not). Use structural induction to prove that S C PAL. In particular, prove that for any s E S, & E PAL. Hint: Note that you're trying to prove s E PAL which on face value isn't of our usual LHS=RHS form. But if you look at the definition of PAL you can find an equivalent statement using LHS=RHS