Question

Difference between pushdown automata and turing machine

Answer 1

A PDA can only access the top of its stack, whereas a TM can access any position on an infinite tape. The infinite tape cannot be simulated with a single stack, so a PDA is less computationally powerful -- there are algorithms that can be programmed with a TM that cannot be programmed with a PDA. An automaton with access to two stacks rather than just one can simulate a TM and thus has equivalent computational power.

The language of any context-free grammar (Chomsky type 2) can be recognized by some non-deterministic PDA. The language of any formal grammar (Chomsky type 0) can be recognized by some TM. The latter are a strict superset of the former.

Answer 2

Pushdown automation:  

Pushdown automation is a branch of theory based computer science and it is a type of automation that uses a stack. Pushdown automation is used in theories that cannot be calculated by computers. Pushdown automation is less capable than Turing machines. Pushdown automation reads a given input string from left to right. It can also manipulate a string.

Turing machine:

A Turing machine is a hypothetical computer used to demonstrate that there are a type of issues that no compters can solve regardless of whether it has boundless time and limitless memory. The basic Turing machine has a data memory composed of infinitely long tapes composed of cells. A “head” is positioned on one cell and can read its current symbol, write a new symbol, step backward/forward one cell.