• Main page

Chapter 1

Machines

This is a course on Languages, Automata and Computation. We have to start somewhere, and 'a' is before 'c' or 'l' so let's start with automata!

'Automata' (singular: automaton) is a Greek word for 'machines'. The automata in this course are all discrete rather than continuous machines. Or perhaps one should say digital-rather-than-analogue. If you are not happy about this difference go away and ask your supervisor before you read any further. If you are happy about this difference just check that you and I have the same take on it: a car is an analogue machine, and a computer is a digital machine.

There are two ways into machines, and one can profitably run both - one does not have to choose one.

• One can draw a couple of FSAs and talk through what they do.


• One can start with a well-motivated story from life and say how this might be a machine. Try for example:
  http://www.philosophy.uncc.edu/logic/projectTALLC/tallc2/applets/puzzles/wj/wj_jar.html
  or try googling 'water jugs'

Finite state machines can be quite useful in describing games, like chess, or Go, or draughts. This is because many games (for example, those I have just mentioned) have machines naturally associated with them: the board positions can be thought of as states of a machine. It's not always clear what the input alphabet is!

The point of departure is this: machines are things with finite descriptions that have states, and they move from one state to another on receiving an input, which is a character from an input alphabet.

To be formal about it: A machine ℳ is a set S of states, together with a family of transition operations, one for each w ∊ Σ, the input alphabet. These transition operations are usually written as one function of two arguments rather than lots of unary operations. Thus δ(s, c) is the state that that machine is in after it received character c when it was in state s:    δ : S × Σ → S.

There must of course be a designated start state s₀ ∊ S, and there is a set A of accepting states A ⊆ S, whose significance we will explain later. We will also only be interested in machines with only finitely many states. There are technicalities to do with infinity, but we don't need to worry about them just yet. All we mean is that for our machine ℳ the number | S | (the size of the set of states) must be a natural number: | S | = 1 or | S | = 2 or . . . .