Problem
1. Suppose T is a TM accepting a language L. Describe how to construct a nondeterministic TM accepting L∗
2. Describes a PDA accepting the language Pal. Draw a TM that accepts this language by simulating the PDA. You can make the TM nondeterministic, and you can use a second tape to represent the stack.
3. Describe informally how to construct a TM T that enumerates the set of palindromes over {0, 1} in canonical order. In other words, T loops forever, and for every positive integer n, there is some point at which the initial portion of T 's tape contains the string
ΔΔ0Δ1Δ00Δ11Δ000Δ ... Δxn
where xn is the nth palindrome in canonical order, and this portion of the tape is never subsequently changed.