simulation of PDA with 2-tape Turing machine [closed]

Question

Can someone give me suggestions how can I construct a 2-tape Turing machine which simulates PDA ?

Answer 1

The first tape for input and the second for storing symbols (like on a stack). The first tape should be read-only so that the TM reads symbols one by one from left to right.

Every time your PDA writes a symbol on the stack, your TM moves the second head right and writes a symbol on the rightmost empty cell. When the PDA removes a symbol from the stack the TM replaces the rightmost symbol with the blank symbol (erases) and moves the second head left. On each state transition the first head should always move right.

In addition, your TM shouldn't be allowed to arbitrarily move heads right and left violating PDA rules.

Consider the following formal definition of moves for PDA (assume deterministic for simplicity):

UPDATE

Definition of PDA moves

$\delta(q, a, Z) = (p, \alpha)$: the PDA in state $q$ with input $a$ and $Z$ on the top of the stack. The PDA enters the state $p$ and replaces the top symbol $Z$ with the symbols of the string $\alpha$. So, $\delta(q, a, Z) = (p, \epsilon)$ means remove the top stack symbol (pop). Advance the input head one symbol.

$\delta(q,\epsilon, Z) = (p, \alpha)$: the PDA in state $q$ with $Z$ on the top of the stack. Independent of the input symbol, PDA enters the state $p$ and replaces the top symbol $Z$ with the symbols of the strings $\alpha$. Input head does not advance in this case.

Examples of translation of PDA moves into TM moves

Example 1. PDA move $\delta(q_1, 0, A) = (q_2, B)$ is translated as: TM in state $q_1$, head 1 (input head on the tape 1) reads $0$, and head 2 (stack head on the tape 2) reads $A$. Replace $A$ with $B$ (head 2 writes the symbol $B$ while it is on $A$). Advance head 1 one symbol. Enter state $q_2$.

Example 2. $\delta(q_1, 0, A) = (q_2, BC)$ is translated as: TM in state $q_1$, head 1 reads $0$, and head 2 reads $A$. Head 2 writes $B$ (replaces $A$), advances head 2 one symbol, TM enters state $q_{21}$. Then, while TM in state $q_{21}$ and head 1 reads $0$, and head 2 reads the blank symbol: head 2 writes symbol $C$, enters state $q_2$. Advance head 1 one symbol.

The basic idea: in order to write $BC$ we introduced a new state $q_{21}$.

Analogously, $\delta(q,\epsilon, Z) = (p, \alpha)$ means head 2 just writes the blank symbol and moves left.

$\delta(q,\epsilon, Z) = (p, \alpha)$ means that you define the same transition for every input symbol.

This is how a multitape Turing machine is defined.