Consider the language A of all palindromes over a b Describe

Consider the language A of all palindromes over {a, b}. Describe a TM T that decides A. Use the format and level of detail of the description of M_1 at the top of page 167. Draw the state diagram of T. You do not need to include the rejecting state.

Solution

a> Truning Machine:
Blank symbol B

(i,B)     = (t,B,R)   accept if tape is Blank
(i,a)    = (pa,B,R)   delete a at LHS; look for a at RHS
(i,b)    = (pb,B,R)   delete b at LHS; look for b at RHS
(pa,a)   = (pa,a,R)   move to RHS
(pa,b)   = (pa,b,R)
(pb,a)   = (pb,a,R)
(pb,b)   = (pb,b,R)
(pa,B)   = (qa,B,L)   found RHS; now check whether a or b
(pb,B)   = (qb,B,L)
(qa,a)   = (r,B,L)   check RHS=a; delete it
(qb,b)   = (r,B,L)   check RHS=b; delete it
(qa,B)   = (t,B,R)   accept if all tape is Blank
(qb,B)   = (t,B,R)
(r,a)   = (r,a,L)   return to LHS
(r,b)   = (r,b,L)
(r,B)   = (i,B,R)   found LHS; reurn to state i