Question

What is the difference between finite state machine and pushdown automata and turing machine?

Answer 1

a)A finite state machine is just a set of states and transitions. The only memory it has is what state it is in. Thus, the number of memory states is... finite.

b)A Turing machine is a finite state machine plus a tape memory. Each transition may be accompanied by an operation on the tape (move, read, write). Its total possible configurations is arbitrarily large, regardless of the size of the program; it expands towards infinity.