Finite State Machines

A finite state machine is defined by

a set of inputs
a set of states
a set of outputs
a set of maps from states and inputs into states and outputs
{state, input} -> {state, output}
an initial state

As an example, let us describe the sequence of events which takes place when you answer the telephone. For this example, we will assume that you do not have an answering machine or services such as call waiting.

We begin the process by waiting for the telephone to ring; during this time, we are in a wait state, which we will designate W.
When the phone rings, you pick up the handset and change to the answer state (designated A).
At this point, one of four things may happen:
- the person making the call asks for you;
- the person making the call asks for someone who is currently at home;
- the person making the call asks for someone who is currently not at home;
- it is a wrong number.
If the call is for you, you say hello and change to the talking state (designated T).
If the call is for someone who is currently at home, you tell the person making the call to wait and move to a state where you are getting the person they desire (designated G).
If the call is for someone who is currently not at home, you tell the caller and change to the state where you are taking a message (designated M).
If it is a wrong number, you tell the caller and move to the state where the call is finishing (designated F).
Once in the talking state, whenever the caller talks you reply and stay in the talking state.
If however, the caller says goodbye, you say goodbye and move to the finish state.
If you were in the state where you were getting someone else to come to the phone, when they arrive they say hello and enter the talking state.
If you are taking a message and the caller says goodbye, you say goodbye and move to the finish state.
Once in the finish state, when the caller hangs up, you hang up the handset and change to the wait state.

We represent this sequence as a finite state machine as follows:

the set of inputs is
{ring, call is for you, call is for someone currently at home, call is for someone not currently at home, call is a wrong number, person you are getting comes to the phone, caller talks, caller says goodbye, caller hangs up}
the set of states is
{waiting for a call (W), answering the phone (A), talking (T), getting someone else to come to the phone (G), taking a message (M), finishing the call (F)}
the set of outputs is
{picking up the phone, saying hello, telling the caller to wait, telling the caller that the person they requested is not at home, telling the caller that they have dialed a wrong number, replying to the caller, saying goodbye, hanging up the handset}
the set of maps was described in the sequence above
the initial state is the wait state (W)

We can represent this finite state machine as a labeled directed graph where

the states are represented by vertices
the arcs represent state transitions and are labeled with inputs and outputs (here we have omitted the outputs for reasons of clarity):

When a finite state machine is represented as a directed graph, the matrix representation is called a state table. Here, rows are labeled by states, the columns are labeled by inputs, and the matrix elements consist of the outputs and the next state to move to:

. ring for you at home not at home wrong number comes to phone caller talks goodbye hangup

wait (W) pick up, A . . . . . . . .

answer (A) . hello, T wait, G tell them, M tell them, F . . . .

talk (T) . . . . . . reply, T goodbye, F .

get person (G) . . . . . hello, T . . .

take msg (M) . . . . . . . goodbye, F .

finished (F) . . . . . . . . hang up, W

The finite state machine is a formal way to describe an algorithm; in this example, we have given an algorithm for answering the telephone. When the algorithm is applied to an actual series of inputs, we can construct a table which illustrates the sequence of states entered by the machine as it processes the algorithm. For instance, in the case of a wrong number, the sequence of inputs and states is

input output next state

ring pick up phone A

wrong number tell them F

hangup hang up phone W

while in the case where the caller talks to someone other than the person who answers the sequence is

input output next state

ring pick up phone A

at home ask them to wait G

comes to phone say hello T

talks reply T

talks reply T

talks reply T

says goodbye say goodbye F

hangs up hang up phone W

These tables are often summarized in the form of a sequence of states, ie.:

A, F, W

and

A, G, T, T, T, T, F, W

respectively. They can also be summarized as a sequence of outputs:

pick up phone, tell them (it's a wrong number), hang up phone

and

pick up phone, ask them to wait, say hello, reply, reply, reply, say goodbye, hang up phone

respectively

When you learn about networking, you will find that the finite state machine is the common language for describing networking protocols, especially in TCP/IP, where our example in this section is very similar to the finite state machine which describes the establishment of a TCP connection.

The section concludes our discussion of graph theory. In the next chapter, we begin the quantitative measurement of computer capacities and performance with a discussion of units of measurement.

Go to: Title Page Table of Contents Index

Please send comments or suggestions to the author.

.	ring	for you	at home	not at home	wrong number	comes to phone	caller talks	goodbye	hangup
wait (W)	pick up, A	.	.	.	.	.	.	.	.
answer (A)	.	hello, T	wait, G	tell them, M	tell them, F	.	.	.	.
talk (T)	.	.	.	.	.	.	reply, T	goodbye, F	.
get person (G)	.	.	.	.	.	hello, T	.	.	.
take msg (M)	.	.	.	.	.	.	.	goodbye, F	.
finished (F)	.	.	.	.	.	.	.	.	hang up, W

input	output	next state
ring	pick up phone	A
wrong number	tell them	F
hangup	hang up phone	W