Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
Your idea is correct (or at least one way of doing it), though it may be "easier" to add a third tape, where you just write the current PDA state. Your transition function just needs to simulate the PDA. The alphabet for the input tape is just the PDA's input alphabet plus the blank, the alphabet for the stack tape is the stack alphabet plus the blank symbol. You read a symbol on the input tape, the PDA state and the current symbol on the stack, move the input head right and maybe write a symbol on the stack tape and stay put, write a symbol and move right, or erase a symbol and move left. The state tape head just stays put and writes the new state on the tape. If you read a blank on the input tape, and the current PDA state is accepting, move to the TM's accept state, if you otherwise read a blank on the input tape, then move to the TM's reject state.
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$.
This gives you a TM with a single state that does all the real work, and the accept and reject states.
