How to simulate a non-deterministic PDA with a turing machine?
4
$\begingroup$
$\endgroup$
-
$\begingroup$ What did you try? Where did you get stuck? It might help to think of Turing machines as a very basic programming language. $\endgroup$ – David Richerby May 11 '15 at 22:14
-
$\begingroup$ I'm trying to simulate it without using turing machine with non- deterministic moves, and i didn't find a way to do it. $\endgroup$ – odu9 May 11 '15 at 22:58
-
1$\begingroup$ 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 $\endgroup$ – Thomas Klimpel May 11 '15 at 22:59
-
1$\begingroup$ 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. $\endgroup$ – Thomas Klimpel May 11 '15 at 23:02
3
$\begingroup$
$\endgroup$
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:
- Convert $G$ to an equivalent grammar in Chomsky normal form.
- 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.
- If any of these derivations generate $w$, $accept$; otherwise, $reject$."
-
$\begingroup$ Just directly simulating the PDA seems like a much simpler solution but OK. $\endgroup$ – David Richerby May 12 '15 at 16:11
-
$\begingroup$ but if the pda was non-deterministic , what would you do? @DavidRicherby $\endgroup$ – odu9 May 12 '15 at 21:49
-
$\begingroup$ @odai Simulate it on a nondeterministic Turing machine and optionally use standard constructions to determinize the result. $\endgroup$ – David Richerby May 12 '15 at 21:57
-
$\begingroup$ @DavidRicherby yes true, thanks , note that "muratcakamk" answer is also intresting. $\endgroup$ – odu9 May 12 '15 at 22:44
3
$\begingroup$
$\endgroup$
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.
-
1$\begingroup$ 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) $\endgroup$ – odu9 May 12 '15 at 6:48
-
1$\begingroup$ 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. $\endgroup$ – Ran G. May 12 '15 at 14:09
