Idealised machines

It’s useful to think of various types of idealised machines, with varying levels of complexity, and classify computations by which of these idealised machines can perform them.

In this classification there’s a maximally powerful machine, which should be able to perform any calculation which can be performed. This is called a Turing machine. Those will be described much later in the module.

The simplest useful machine in this hierarchy is what’s called a finite state automaton. It has a single state variable, which can take only finitely many values, and must read its input one token at a time without backtracking. Our grammar checker for the postfix version of our language barely fails to qualify. Its state is completely described by the counter but it can take any non-negative integer as its value and there are infinitely many non-negative integers.

A finite state automaton can be conveniently illustrated by a directed graph, where vertices correspond to possible states and edges correspond to the allowed state transitions. More information is needed to give a complete description of the finite state automaton, like which state is the initial state and which tokens in the input cause which state transitions. The accompanying figure gives an example.

We’ll discuss such diagrams in more detail later but I’ll give a quick explanation now. The alphabet excepted by this finite state automaton is the symbols P, S, A and G. Each state corresponds to a vertex, indicated by a circle or a double circle. The doubly circled vertices are accepting states, which means that if we are in one of those states when the input ends then the input is accepted. If the input ends when we’re at a singly circled vertex then it is rejected. Each possible transition is indicated by an edge, i.e. an arrow. These edges are labelled by the symbols which cause the transition. The initial state is the one on the left with the arrow from nowhere.

Intermediate in complexity between the finite state automaton and the Turing machine is what’s called the pushdown automaton. This is an idealised machine whose only data structure is a single stack. Like the finite state automaton it must read its input one token at a time. The state of the machine is fully described by the contents of this stack. Our postfix module selection procedure is an example of a pushdown automaton.

There are a variety of visual representations of pushdown automata but none seem to be as standard as the one for finite state automata.