Consider the language L2 = { w#wrev | w ? {0, 1}* and wrev denotes the reverse of the string w}...

Consider the language L2 = { w#w^{rev} | w ? {0, 1}* and
w^{rev} denotes the reverse of the string w}. defined over
the alphabet S = {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.