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


closed as unclear what you're asking by Evil, David Richerby, Rick Decker, Juho, hengxin Jul 9 '17 at 13:00

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Have one tape simulate the stack. $\endgroup$ – Yuval Filmus Jun 24 '17 at 18:18
  • $\begingroup$ Yeah . But how can I transform instructions in which I have to put more than one symbol on the second tape ( which is simulation of the stack ) ? $\endgroup$ – unnamed Jun 25 '17 at 12:37
  • $\begingroup$ Be creative. Simulate them using more than one step. $\endgroup$ – Yuval Filmus Jun 25 '17 at 13:00
  • $\begingroup$ maybe I should go to a state in which I dont move in the first tape only on the second so I can write all the characters on the second tape $\endgroup$ – unnamed Jun 25 '17 at 13:05

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):


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.

  • $\begingroup$ But for some of the PDAs they can write more than one symbol on the stack in one "move" How can I translate this to my Turing Machine ? $\endgroup$ – unnamed Jun 25 '17 at 12:34
  • $\begingroup$ Move right. Write. Move right. Write. $\endgroup$ – fade2black Jun 25 '17 at 12:38
  • $\begingroup$ Ok . I want to make it with a 2 tape TM . My second tape is my stack . So for example for a PDA instruction such as paA - > pAAA how can I translate it to , a TM instruction . I have to read a from first tape and A from second . first go to right and the second go also to right and should right 2 more As . But In the TM instruction I think we can only make one move per instruction and write only one character . Thats why I'm not sure how to "transform" such PDA instructions into TM instructions $\endgroup$ – unnamed Jun 25 '17 at 12:44
  • $\begingroup$ I translate PDAs instruction which have the form : zaA -> z'epsilon into TM instruction : (z,(a,A)) -> (z' ,(a,Blank),(R,L)) $\endgroup$ – unnamed Jun 25 '17 at 12:54
  • $\begingroup$ @StenIvanov, please see updates. $\endgroup$ – fade2black Jun 25 '17 at 18:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.