Question

Differentiate between PDA and TM with respect to: halt state and final state

Answer 1

Answer:

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.

Answer 2

Answer:

Answer. 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