Finite State Machine

We have used finite state machines (FSMs) a few times so far in this class. They are a convenient way of organizing the tasks for our embedded system while making sure that we account for all possible inputs and keeping track of state. When implemented correctly using non-blocking coding practice, they also enable scalability so that we can operate numerous state machines roughly in parallel.

In this problem we'll examine some aspects of state machines a bit more abstractly. No implementation here, but let's work through the logic.

Note that there are oodles of information about state machines online, as they are used in many contexts. You'll also see them in many classes in Course 6, introduced and used quite formally. We've been a bit informal here, since we want you to see the need for state machines arise naturally from the projects we're trying to do. There is a pretty interesting embedded systems perspective on state machines here.

A properly constructed state machine has inputs, state, and outputs. For example, in our work in Lab 01B, the input was whether the button was pressed or not along with some timer variables, the state was one of several that you designed, and the output was generally the output on the LCD. In a properly formulated state machine, we should be able to determine the next state and outputs given the current state and inputs. We should also not have an undefined set of inputs and state, which would lead to undefined behavior.

The term Finite State Machine refers to a system with a finite number of states. Finite state machines have been what we've been creating so far in this class when working with buttons and some things in our labs.

Let's explore making a thermostat that uses two buttons to switch states. Here's the initial state diagram for this system. The transitions have a tuple associated with them that refers to the button presses: (button 1, button 2). The buttons in this exercise are Active High, which is different from lab. If the value is 1 it means that button was pressed. Ignore how we determine a button press and issues like debouncing or adding delays or something.

We have three state variables associated with the system, these are our outputs. One is set_point, which is an integer denoting the set-point temperature (i.e., what temperature we want the room to be at). We also have a boolean state variable C_F which will tell the display whether to show the temperature in degrees Fahrenehit or Celcius. And a state variable controlling, which is an int that cycles between states 0 (OFF), 1 (ON), and 2 (controlled).

We don't explicitly show the (0,0) inputs, which cause no state transition. Also some arrows have no marker. That means that we always follow that arrow on the next timestep/transition, regardless of the inputs (including (0,0) inputs).

You can imagine that there is additional code to actually control the temperature, for example by reading a temperature sensor, comparing it to the set point, and turning the heater on and off. We'll ignore that part for now.

Our state machines are synchronous state machines, meaning that inputs are read and state changes occur every time through the loop. Only one state change may occur in each loop iteration.

We should now be able to determine the state and output given any sequential series of inputs. For example, if we are in state 0 and receive an input of (1,1), we'll go to state 6 and not change the state variables (which are our outputs). If our next input is (0,1), we'll go to state 7 and controlling = 0.

For the following questions below, enter a Python tuple containing the final (state, set_point, C_F, controlling), where all variables will be integers (0 = boolean 0, 1 = boolean 1). Note that, if a state makes changes to set_point, C_F, or controlling, those changes occur immediately upon entry into that state. Also, state 0's initialization of all the variables only occurs once (we don't reset the variables every time we return to state 0).

Starting in the base state, what is the final state and outputs when the following inputs occur: (0,1), (0,1). These inputs occur on consecutive loop iterations.

Starting in the base state, what is the final state and outputs when the following inputs occur: (1,1), (0,1) (0,1) (0,1). These inputs occur on consecutive loop iterations.

Starting in the base state, what is the final state and outputs when the following inputs occur: (1,0) (1,0) (1,1) (1,0) (0,1) (1,1) (0,1) (0,1) (0,1) (1,0). These inputs occur on consecutive loop iterations.

One purpose of state machine formalism is that we can pinpoint situations that lead to dead ends, or unspecified behavior. For example, once we go to state 6, there doesn't appear to be a way to get back to state 0. Worse, state 6 has no specified behavior for inputs of (1,0) or (1,1).

Which other state has an unspecified behavior on some input?