Consider the language L2 = { w#w^rev | w {0, 1}* and w^rev denotes the reverse of the string w}. defined over the alphabet = {0, 1, #}.

1. Give a single tape turing machine that recognizes L.

2. Give a pushdown automaton that recognizes L.

3. Give a multi-tape turing machine that simulates the pushdown automaton that you have provided in part 2). Since writing a full formal description of a multi-tape turing machine is difficult, precise English description of each step (or a set of steps, also referred as a batch) suffices.