# 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.

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:

• 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.

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:

• 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

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.
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

• the Java Virtual Machine, which runs the applets;
• the browser, which runs the JVM;
• the operating system under which the browser runs, and
• the CPU chip, which runs the instructions defined by all of the above "machines".

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.