The finite state machine

There are remarkably few fundamental concepts that you need to know about to understand what a digital computer does and how it operates. One of the most important concepts is discrete, which lies at the heart of both computer operation and computer programs.

Computers operate on discrete data elements – that is, elements whose values are chosen from a fixed and finite range of values. We use discrete values in everyday life – for example, the letters of the Roman alphabet that belong to the set {A...Z}. A letter is never between two possible values. It’s the same with the days of the week; you can have one of seven days, but you can’t have a day that is slightly Monday or just a little bit bigger than Wednesday. In the case of computers, the fundamental data element is the bit, which can only have values of 0 or 1, and all its data structures are represented by strings of 1s and 0s.

As well as discrete data values, we can have discrete points in time. Imagine that time moves in one direction, from one discrete point to another discrete point. Nothing exists between two discrete points in time. It’s a bit like a digital clock that goes from 12:15:59 to 12:16:00. There’s nothing in between.

Now, imagine state space, which is a grandiose term for all the states a system can be in (for example, a plane can be in the climbing, descending, or level flight state). States are a bit like time, except that you can go forward or backward between discrete points in state space. If there are a limited number of possible states, a device that models the transitions between states is called a finite state machine (FSM). An elevator is a finite state machine: it has states (position at the floors, doors open or closed, and so on) and inputs (the elevator call buttons, floor selection buttons, and door open and close buttons).

Before we take a serious look at FSMs, let’s begin with a simple example of how to use FSMs to describe a real system. Consider the TV of yesterday, which is a device with two states: on and off. It is always in one of these two states, and it can move between these states. It is never in a state that is neither on nor off. Modern TVs often have three states – on, standby, and off– where the standby state provides a fast-on mechanism (that is, part of the electronics is in an active on state, but the display and sound system are powered down). The standby state is often called the sleep state or idle state. We can model discrete states using a diagram. Each state is represented by a labeled circle, as demonstrated in Figure 1.1:

Figure 1.1 – Representing the three states of a television

Figure 1.1 shows the three states, but it doesn’t tell us the most important information we need to know: how we move between states. We can do this by drawing lines between states and labeling them with the event that triggers a change of state. Figure 1.2 does this. Please note that we are going to construct an incorrect system first to illustrate some of the concepts concerning FSMs:

Figure 1.2 – Representing the states of a television with transitions

In Figure 1.2, we labeled each transition by the event that triggers it; in each case, it’s pressing a button on the remote controller. To go from off to on, you have to first press the standby button and then the on button. To go between on and standby, you must press the on button or the standby button.

We’ve forgotten something – what if you are already in a state and you press the same button? For example, let’s say the TV is on, and you press the on button. Also, what’s the initial state? Figure 1.3 rectifies these omissions.

Figure 1.3 has two innovations. There is an arrow to the off state marked Power on. This line indicates the state the system enters when you first plug it into the electricity supply. The second innovation in Figure 1.3 is that each state has a loop back to itself; for example, if you are in the on state and you press the on button, you remain in that state:

Figure 1.3 – The TV control with initialization

The state diagram shown in Figure 1.3 has both a logical error and an ergonomic error. What happens if you are in the off state and press the on button? If you are in the off state, pressing the on button (in this system) is incorrect because you have to go to standby first. Figure 1.4 corrects this error by dealing with incorrect inputs:

Figure 1.4 – The TV control with wrong button correction

Figure 1.4 now provides correct operations from any state and includes the effect of pressing buttons that cause no change of state. But we still have the ergonomic error – that is, it’s a correct design that behaves in a way that many would consider poor. The standby state is a convenience that speeds up operations. However, the user does not need to know about this state – it should be invisible to the user.

Figure 1.5 demonstrates the final version of the controller. We’ve eliminated a standby button, but not the standby state. When the user presses the on button, the system goes directly to the on state. However, when the user presses off when in the on state, the system goes to the standby state. From the standby state, pressing the on button results in the power on state, while pressing off results in the power off state. Note that the same action (pressing off) can have different effects, depending on the current state:

Figure 1.5 – The TV control with a hidden standby state

We’ve labored with this example because the notion of FSMs is at the heart of all digital systems. All digital systems, apart from the most trivial, move from state to state, depending on the current input and past states. In a digital computer, the change-of-state trigger is the system clock. A modern computer operating at a clock speed of 4 GHz changes state every 0.25 x 10-9 s or every 0.25 ns. Light traveling at 300,000 km/s (186,000 mph) moves about 7.5 cm or 3 inches during a clock cycle.

Traffic lights example

Let’s look at a second example of an FSM. A classic example of an FSM is traffic lights at a crossroads. Consider an intersection with traffic moving north-south or east-west. The traffic may move in only one direction at a time. Assume that this is a system with a clock and a change of state is permitted every minute:

Current State of the Lights	Traffic in the North-South Direction	Traffic in the East-West Direction	Action to Be Taken On the Next Clock	Next State of the Lights
North-south	None	None	No traffic, no change	North-south
North-south	None	One or more	East-west, forces change	East-west
North-south	One or more	None	North-south, no change	North-south
North-south	One or more	One or more	East-west, forces change	East-west
East-west	None	None	No traffic, no change	East-west
East-west	None	One or more	East-west, no change	East-west
East-west	One or more	None	North-south, forces change	North-south
East-west	One or more	One or more	North-south, forces change	North-south

Table 1.1 – Traffic lights sequence table

Suppose the traffic is currently flowing north-south. At the next clock, it may either remain flowing north-south or the lights may change to allow east-west traffic. Similarly, if traffic is flowing east-west, at the next clock, it may either remain flowing east-west or the lights may change to permit north-south traffic.

We can use Table 1.1 to describe this system. We have provided the current state of the lights (direction of traffic flow), indicated whether any traffic had been detected in either the north-south or east-west direction, the action to be taken at the next clock, and the next state. The traffic rule is simple: the lights remain in their current state unless there is pending traffic in the other direction.

We can now convert this table into the FSM diagram shown in Figure 1.6. Note that we have made the east-west state the power on state; this is an arbitrary choice:

Figure 1.6 – A finite state machine for Table 1.1

What have we learned? The most important point is that a system is, at any instant, in a particular state and that a transition to another state (or a transition back to the current state) is made according to a defined set of conditions. The FSM has several advantages, both as a teaching tool and a design tool:

• It uses a simple intuitive diagram to describe a system with discrete states
• The state transition diagram (if correct) provides a complete and unambiguous way of describing a system
• The FSM is also an abstract machine in the sense that it models a real system, but we don’t have to worry about how the FSM is implemented in real hardware or software
• Any FSM can be implemented either in hardware or software; that is, if you can define a state diagram on paper, you can build the circuit in dedicated hardware or write the program to run on a general-purpose computer

I have included a brief introduction to FSMs because they can be considered a precursor to the digital computer. An FSM is designed to carry out a specific task; this is built into its hardware. A computer has some of the characteristics of an FSM but you can program the transitions between states.

Solving a simple problem algorithmically

Now that we’ve introduced FSMs, we will describe a problem, solve it, and then construct our computer. A bag contains a mixture of red and white tokens. Suppose that we take a token at a time out of the bag and continue until we have removed three consecutive red tokens. We want to construct an algorithm that tells us to stop removing tokens from the bag when three reds in a row have been detected.

Before creating an algorithm, we’ll provide an FSM for this problem:

Figure 1.7 – FSM for a three-token detector

As you can see, there are four states. We begin in state S0. Each time a token is received, we move to the next state if it’s red, and back to the initial state if it’s white. Once we’ve reached state S3, the process ends. Now, we’ll perform the same operation algorithmically.

If a white token is represented by the symbol W, and a red token by R, a possible sequence of tokens might be RRWRWWWWRWWRRR (the sequence is terminated by the three Rs). An algorithm that tells us when to stop removing tokens can be written in the following form:

• Line 1: Get a token from the bag
• Line 2: If the token is white, then go back to line 1
• Line 3: Get a token from the bag
• Line 4: If the token is white, then go back to Line 1
• Line 5: Get a token from the bag
• Line 6: If the token is white, then go back to Line 1
• Line 7: Success – three consecutive red tokens have been taken out of the bag

As you can see, the algorithm is expressed in plain English. It is read from top to bottom, line by line, and the action specified by each line is carried out before the next line is processed. In this algorithm, each line has a unique name (that is, Line 1, Line 2, and so on). Labeling a line enables us to refer to it; for example, when the algorithm states that we must go back to Line 1, this means that the next step to be carried out is specified by Line 1, and we continue carrying out actions from Line 1 onward. This algorithm is not entirely satisfactory – we haven’t checked that the bag contains only red and white tokens, and we haven’t dealt with the situation in which we run out of tokens before we locate the sequence we’re looking for. At the moment, we are not concerned with these details.

There’s no single solution to this problem – more often than not, lots of algorithms can be constructed to solve a given problem. Let’s derive another algorithm to detect a sequence of three consecutive red tokens:

Line 1: Set the total number of consecutive red tokens found so far to 0

Line 2: Get a token from the bag

Line 3: If the token is white, then go back to Line 1

Line 4: Add 1 to the number of consecutive red tokens found so far

Line 5: If the number of consecutive red tokens is less than 3, then go back to Line 2

Line 6: Success – 3 consecutive red tokens have been taken out of the bag

This algorithm is more versatile because it can easily be modified to detect any number of consecutive red tokens simply by changing the value of 3 in Line 5 of the algorithm.

Figure 1.8 presents this algorithm diagrammatically in the form of a flowchart that shows the sequence of operations that take place when executing an algorithm. Lines with arrowheads indicate the sequence in which operations are carried out. Boxes indicate the actions themselves, and diamonds represent conditional actions. The expression in the diamond is evaluated to yield either “yes” or “no,” and control flows in one direction or another. In general, flowcharts are well suited to depicting simple algorithms, but they are regarded as very unsuitable for complex algorithms. A flowchart for a complex algorithm looks like a bowl of spaghetti – but without the spaghetti’s inherent clarity and organization.

Figure 1.8 – An algorithm represented by a flowchart

Constructing an algorithm

The next step is to provide an algorithm that tells us how to solve this problem clearly and unambiguously. As we step through the sequence of digits, we will need to keep track of what’s happening, as Table 1.2 demonstrates:

Position in sequence	0	1	2	3	4	5	6	7	8	9	10	11	12	13
New token	R	R	W	R	W	W	W	W	R	W	W	R	R	R
Is it red?	Y	Y	N	Y	N	N	N	N	Y	N	N	Y	Y	Y
Number of reds	1	2	0	1	0	0	0	0	1	0	0	1	2	3

Table 1.2 – A sequence of tokens selected at random

Pseudocode is a term that’s applied to a method of expressing an algorithm in something that falls between plain English and a formal programming language. The following pseudocode expresses the actions we need to perform. The initialization operations that we perform once at the beginning are in normal typeface, while the repetitive actions defined by REPEAT...UNTIL are in bold. We will look at these operations in detail when we introduce Python:

1.    Set numRed to 0
2.    Set maxRed to 3
3.    REPEAT
4.        Get a token
5.        IF its color is red
6.        THEN numRed = numRed + 1
7.        ELSE numRed = 0
8.    UNTIL numRed = maxRed

This pseudocode employs two constructs found in many high-level computer languages: the REPEAT...UNTIL construct in lines 3 to 8, and the IF...THEN...ELSE construct on lines 5 to 7. REPEAT...UNTIL lets you carry out an action one or more times, while IF...THEN...ELSE lets you choose between one of two possible courses of action.

The IF...THEN...ELSE construct is central to the operation of digital computers and you will encounter it many times in this book.

The next step is to introduce Python so that we can write a program to implement this algorithm. Then, we can start to look at the computer. The following code shows a Python program and its output when executed. We haven’t introduced Python yet. The purpose of this program is to demonstrate how close it is to the preceding algorithm and the simplicity of Python:

Sequence =['W','R','R','W','R','W','W','W','W','R','W','W','R','R','R']
numRed = 0
maxRed = 3
count  = 0
while numRed != maxRed:
    token = sequence[count]
    if token == 'R':
        numRed = numRed + 1
    else: numRed = 0
    print('count', count,'token',token,'numRed',numRed)
    count = count + 1
print('Three reds found starting at location', count - 3)

The while numRed != maxRed: line means carry out the block of indented operations, so long as (while) the value of numRed is not equal to maxRed. The != Python operator means not equal.

This is the output when the program is executed. It correctly identifies three consecutive reds and indicates the location of the first run in the run of three:

count  0 token  W numRed 0
count  1 token  R numRed 1
count  2 token  R numRed 2
count  3 token  W numRed 0
count  4 token  R numRed 1
count  5 token  W numRed 0
count  6 token  W numRed 0
count  7 token  W numRed 0
count  8 token  W numRed 0
count  9 token  R numRed 1
count 10 token  W numRed 0
count 11 token  W numRed 0
count 12 token  R numRed 1
count 13 token  R numRed 2
count 14 token  R numRed 3
Three reds found starting at location 12