Finite State Machines

A finite state machine is defined by

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.

  1. 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.
  2. When the phone rings, you pick up the handset and change to the answer state (designated A).
  3. At this point, one of four things may happen:

  4. If the call is for you, you say hello and change to the talking state (designated T).
  5. 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).
  6. 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).
  7. If it is a wrong number, you tell the caller and move to the state where the call is finishing (designated F).
  8. Once in the talking state, whenever the caller talks you reply and stay in the talking state.
  9. If however, the caller says goodbye, you say goodbye and move to the finish state.
  10. 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.
  11. If you are taking a message and the caller says goodbye, you say goodbye and move to the finish state.
  12. 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:

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

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:

.ringfor youat home not at home wrong numbercomes to phonecaller talks goodbyehangup
wait (W)pick up, A........
answer (A).hello, Twait, Gtell them, Mtell 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

inputoutputnext state
ringpick up phoneA
wrong numbertell themF
hanguphang up phoneW
while in the case where the caller talks to someone other than the person who answers the sequence is
inputoutputnext state
ringpick up phoneA
at homeask them to waitG
comes to phonesay helloT
talksreplyT
talksreplyT
talksreplyT
says goodbyesay goodbyeF
hangs uphang up phoneW
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 finite state machine is a very powerful concept: any computation which can be performed in a finite time can be modeled as a finite state machine. Finite state machines are often used in formally describing languages, and in compilers for programming languages. They are also particularly well-suited for asynchronous applications, where the sequence of inputs is independent from the design of the algorithm.

The Java applets which serve homework problems from this text are typical of asynchronous applications. Consider the "Using Finite State Machines" applet which accompanies this section. While there can be more than one finite state machine model for a given program, here is a state graph which models that applet:

In this finite state machine, the states are

{init, wait (for) state prob(lem), process state prob, wait output prob, process output prob},
the inputs (colored red in the graph) are
{(none), check (answer button), next (problem button), same (problem), correct answer, wrong answer},
and the outputs are
{(none), display state problem, display output problem, , display correct, display sorry}.
Two separate sub-graphs were necessary for the "state problem" part of the machine (where the applet asks for the sequence of states), and the "output problem" part of the machine (where the applet asks for the sequence of outputs), because a finite state machine does not "remember" prior states. It shares this lack of memory with Markov Processes, but differs from a Markov Process in that a finite state machine is deterministic: a specific sequence of inputs will always produce the same sequence of outputs. Markov Processes are random, or non-deterministic processes.

Just as the applets are good examples of asynchronous process, so too are

Note that all of these machines are deterministic, although sometimes they do not appear that way because we are not aware of all of the details of every state. Note also that all of them are, at least potentially, infinite loops: they will continue to run unless interrupted (by, for instance, a power failure).

As you can see, it is instructive to draw the digraph associated with a finite state machine. The graph provides a more intuitive representation of the machine, and the pathologies (such as sinks) become immediately obvious. We suggest you draw digraphs for the following machines:

Be sure to label all states and inputs; you may omit the outputs, as we did in our first example, for clarity.

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 PageTable of ContentsIndex

©2013, Kenneth R. Koehler. All Rights Reserved. This document may be freely reproduced provided that this copyright notice is included.

Please send comments or suggestions to the author.