4Finite Automata
The University of Melbourne
We begin our study of computation with a simple model of computation called finite automata.
The most important feature of a finite automaton is that it has a fixed number of states that it can be in. Intuitively, this corresponds to an algorithm that is only allowed to use a constant amount of memory, regardless of input size; think of a program with only a constant number of variables. In particular, it cannot allocate new memory in response to the input.
This restriction makes sense in highly-constrained settings such as low-power sensors, where one has to deal with processing a steady stream of data input over long periods of time.