Finite-state machines, pushdown automatons and Turing machines

Finite-state machines

Finite-state machines

A finite-state machine has \(n\) states. The machine moves through these states through the use of inputs, and the movement between these states can be represented by a graph.

We can represent the machine with table. One axis shows the inputs, the other the states. The cells can be filled with (if available) movements between the states.

Similar to combinatorial logic, but output is the new state.

Pushdown automatons

Pushdown automatons

In a finite-state machine the action of the machine depends on the state, and on the input. In a pushdown automaton it also depends on a third input – stack.

The stack is a list of symbols. It is the first item on the stack which is used to inform the decision.

The actions of a machine in finite-state machine were to move from state to state. In a pushdown automaton, the actions can also affect the stack, and therefore future changes in state.

A pushdown automaton uses a Last-in First-out (LiFo) stack.

Turing machines

Turing machines

A Turing machine is a pushdown automaton where the stack is no longer LiFo.

Church-Turing thesis