Finite State Machines

David M. Clark and W. Ted Mahavier

( Chapter 3: W. Ted Mahavier < E.L. May < K.M. Shannon ¹ )

If each of \(X\) and \(Y\) is a person, then the relation \(X < Y\) indicates that the notes originated with \(Y\) and were subsequently modified by \(X\text{,}\) who takes full responsibility for the current version. While \(Y\) is credited with the genesis of the notes, s/he makes no claim to the accuracy of the current version which may or may not reflect her/his original version.

Chapter 9 Finite State Machines

Imagine a simple radio with three buttons, an ON/OFF button, a CHANNEL button and a VOLUME button.

Figure 9.1. Transition diagram for \(M_1\)

The radio has ten channels and five volume levels:

\begin{equation*} C0, C1, C2, C3, C4, C5, C6,C7, C8, C9, V0, V1, V2, V3, V4. \end{equation*}

Pressing button \(o\) turns it from OFF to ON or ON to OFF. Regardless of whether the radio is ON or OFF, pressing \(c\) advances the channel by one or takes if from C9 back to C0. Regardless of whether the radio is ON or OFF, pressing \(v\) increases the volume by one level or takes if from V4 back down to V0.

The radio can be thought of as having \(2\times 10\times 5 = 100\) different internal states. In state (OFF,C3,V4), pressing \(o\) will change it to state (ON,C3,V4). Then pressing the sequence \(ccvvv\) will change it from there to channel C5 at volume V2, that is, to state (ON,C5,V2).

Problem 9.2.

If the radio is in state (OFF,C8,V1) and you press the input sequence \(ocvvcovo\text{,}\) what state will it be in?

Problem 9.3.

List three different input sequences that will bring it from state (ON,C7,V3) to state (OFF,C2,V0).

A radio like this is an example of a Finite State Machine (FSM). In this chapter we will study somewhat more elaborate Finite State Machines: Finite State Transducers and Finite State Acceptors. FSMs are the simplest class of computing machines. They model the logic of machines which require logic circuitry, but are not usually thought of as computers, such as vending machines, washing machines and toasters.

FSMs are characterized by the fact that their action, at any point in their operation, is completely determined by their current state and their current input. They have no long term memory and are therefore unable to carry out any logical process of reviewing the past or anticipating the future.