4
$\begingroup$

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

$\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$

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$."
$\endgroup$
  • $\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$

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.

$\endgroup$
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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