[Solved]: simulation of PDA with turing machine

Problem Detail: 

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

Asked By : odai

Answered By : muratcakmak

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$."

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42440