# construct a TM from a PDA

Given a PDA $P=(Q,\sum,\delta,q_0,F)$ construct formally a TM that accepts $L(P)$.

My idea is to construct a Turing machine with 2 tapes, one for the input and the other for the stack. Also to add $q_a$ for accept and $q_r$ for reject and to send to $q_a$ if the TM stops on states in $F$ and send to $q_r$ otherwise.

But I am having a trouble to define new the transition function for the TM: $\delta_M$.

• Seems too much like a homework problem. Better for cs.stackexchange.
– Joshua Grochow
May 24 '13 at 16:23

Given a PDA transition $\delta_{PDA}(q_{i}, \sigma, \tau) = (q_{j}, \rho)$ (so moving from state $q_{i}$ to $q_{j}$, with $\sigma$ in the input, popping $\tau$ and pushing $\rho$), the TM transition looks something like $\delta_{TM}(q_{p}, \sigma, \tau, q_{i}) = (q_{p}, (\sigma, R), (\rho, S), (q_{j},S))$ - the notation here is somewhat abused, mostly to group each tapes actions together in order. Transitions that have one or more $\varepsilon$/$\lambda$ in them complicate things a little, the input tape head would not move on an $\varepsilon$, the stack tape head might move left or right, depending on whether it was a pop or push that had the $\varepsilon$.