View source for What is a finite state machine and how does it relate to the traffic example?

Finite state machines (or FSMs) are models of the discrete dynamics of systems that have a finite number of discrete states.  In this case, "state" means mode or location.  The transitions between these modes of operation are events, such as the expiration of a timer or something specific sensed by a sensor.  There are lots of common systems that can be modeled as an FSM, like a washing machine (the states are the different cycles, like rinse and spin; transitions are timer-driven), a toaster (the states are on and off; the transition from on to off is a timer and the off to on is having the lever pushed down), or a train gate (the states are up and down; the transition from up to down is the approach of a train and from down to up is when the train has passed).

The traffic light system for a simple 4-way intersection can also be modeled as an FSM.  If we have an intersection whose lights are driven by a timer only, we have an FSM with two states (if we ignore yellow lights).  The first state is that the E-W street has the green light and the N-S street has the red light, and the second state is the opposite (E-W is red and N-S is green).  The transitions between these two states is simply the expiration of a timer.  A picture of this simple traffic light FSM is shown below.

[[Image:FSMexample.jpg]]

Let's complicate that example a little more by adding sensors that can tell when there are vehicles waiting to the system.  Now, we have the example that was presented in class.  This FSM has four states: two of the states are the same as in the timed example above, and the two new states are copies of the original states, except for their exit transition conditions.  I'll call them "untimed" states.  Let's say we start in the untimed E-W green state.  When a car is sensed on the N-S streets, a transition is taken from the untimed E-W green state to the timed E-W green state.  When the timer expires, the transition to the untimed N-S green state is taken.  The FSM will stay in that state until a vehicle is sensed on the E-W states; when that happens, the FSM will transition into the timed N-S green state, and so on.

We could complicate things even more by adding yellow lights.  You could add them by adding two more (timed) states that would be entered into from the timed red/green states and whose exit transitions would be based on the expiration of a timer. 

--[[User:Braman|Julia Braman]] 16:52, 8 October 2007 (PDT)

[[Category: CDS 101/110 FAQ - Lecture 2-1]]
[[Category: CDS 101/110 FAQ - Lecture 2-1, Fall 2007]]