1. A string x is a palindrome if x = xR, where xR denotes the reversal of x (i.e., the characters of r in reverse order). For example, abba and ababa are palindromes, and abbab and aaba are not palindromes The state diagram below is for a Turing machine that decides the language of palindromes over the alphabet a,b. Complete the diagram by supplying the appropriate transitions of the form "e e', L/R', where e, e' are symbols from the tape alphabet = {a, b, j. As a hint, each of the eight states serves one of the following purposes . The initial, accept, and reject states . After seeing an a (respectively, b) at the left end of the (remaining) input string, move the head to the right end of the (remaining) string . After seeing an a (respectively, b) at the left end, the head is at the right end Move the head to the left end of the (remaining) input string 2 91 42 start- qstart accept reject