1. Design a standard TM to accept L={w{0,1}:w is a palindrome}L={w{0,1}:w is a palindrome}.

2. Design a high-level block diagram of a multitape TM to compute the product of two positive integers aa and bb (in binary). Initially aa is on the first tape, and the read-write head is positioned on the rightmost bit; similarly, bb is on the second tape, and the read-write head is positioned on the rightmost bit. The result should be put on a third tape, and the read-write head should be positioned on the rightmost bit. You may use the building blocks we designed in class, and extra tapes.

3. Let A={R,S:R and S are regular expressions and L(R)L(S)}A={R,S:R and S are regular expressions and L(R)L(S)}. Show that AA is decidable.