3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Have one tape simulate the stack. $\endgroup$ Jun 24, 2017 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, 2017 at 12:37
  • $\begingroup$ Be creative. Simulate them using more than one step. $\endgroup$ Jun 25, 2017 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, 2017 at 13:05

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\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, 2017 at 12:34
  • $\begingroup$ Move right. Write. Move right. Write. $\endgroup$
    – fade2black
    Jun 25, 2017 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, 2017 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, 2017 at 12:54
  • $\begingroup$ @StenIvanov, please see updates. $\endgroup$
    – fade2black
    Jun 25, 2017 at 18:16

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