# simulation of PDA with turing machine

How to simulate a non-deterministic PDA with a turing machine?

• What did you try? Where did you get stuck? It might help to think of Turing machines as a very basic programming language. – David Richerby May 11 '15 at 22:14
• I'm trying to simulate it without using turing machine with non- deterministic moves, and i didn't find a way to do it. – odu9 May 11 '15 at 22:58
• There are many ways to simulate a non-deterministic PDA with a Turing machine in theory. In practice, you may not really bother to simulate every small detail, as long as you get the final decision right. For this, have a look at en.wikipedia.org/wiki/CYK_algorithm – Thomas Klimpel May 11 '15 at 22:59
• The most obvious (but exponential slow) technique for simulating non-determinism deterministically is to replace single states by sets of single states. If this state includes the state of an entire tape of a Turing machine, then you just copy this entire part in its different variations, and don't care about the exorbitant amount of memory and time this procedure takes. – Thomas Klimpel May 11 '15 at 23:02

The sets of all languages that can be represented by a PDA is proper subset of the all languages that can be represented by a Turing Machine.

Turing Machine can imitate any solution for the problem that can be solved.

The high level definition of the Turing Machine that simulates PDA as follows:

A language is context free if and only if some PDA recognize it. (It is provable)

$A_{CFG}$ is a decidable language.(It is also provable)

The TM $S$ for $A_{CFG}$ follows.

$S$ = "On input $<G,w>$, where $G$ is a CFG and $w$ is a string:

1. Convert $G$ to an equivalent grammar in Chomsky normal form.
2. List all derivations with $2n-1$ steps, where n is the length of $w$; except if $n=0$, then instead list all derivations with one step.
3. If any of these derivations generate $w$, $accept$; otherwise, $reject$."
• Just directly simulating the PDA seems like a much simpler solution but OK. – David Richerby May 12 '15 at 16:11
• but if the pda was non-deterministic , what would you do? @DavidRicherby – odu9 May 12 '15 at 21:49
• @odai Simulate it on a nondeterministic Turing machine and optionally use standard constructions to determinize the result. – David Richerby May 12 '15 at 21:57
• @DavidRicherby yes true, thanks , note that "muratcakamk" answer is also intresting. – odu9 May 12 '15 at 22:44

A PDA is a special (degenerated) case of a TM. Specifically, TM can be seen as a PDA whose stack's head can read from within the stack and not only the top of the stack.

Therefore, simulation of a PDA by a TM is trivial.

• no its not trivial , you forgot that a pda can be a non-deterministic , and i want to simulate it with a deterministic turing machine(not non-deterministic TM) – odu9 May 12 '15 at 6:48
• Turing machine can be non-deterministic as well, and the question mentions nothing about deterministic simulation. Even then, the simulation is easy - you run all the choices "in parallel". Each time the PDA makes a non-deterministic choice, and TM replicates it's memory content and continue to run two (or $|Q|$) instances of the PDA, each with a different choice made. – Ran G. May 12 '15 at 14:09