<-MACHINE->

“Finite State Machines” is one of those terms that I’ve heard mentioned but never found the time to look into. Now that I’ve finished my three months at the Flatiron School I figured that I would give it a look.

Finite state machines (FSM), aka Finite State Automata (ooooh, I like that better!) are machines that inhabit one of a finite number of states at a given time and answer the questions:

1. “What are all the distinct states of the system?”

2. “To what stimuli will the system respond in a given state?”

3. “What state will the system be in if it is presented with a given stimulus in a given state?”

4. “What sequence of inputs are needed so that the system will be in a particular state?”

A finite state machine is defined by it’s states and the triggering conditions for each transition where ‘state’ describes the status of a system waiting to execute a transition and a ‘transition’ is a set of actions to be executed when a condition is fulfilled or when an event is received. Some FSM also allow an action to be associated with a state. An entry action is an action executed when transitioning into a state while an exit action executes when transitioning to a new state.

So What Does All That Mean?

This is my (albeit new and limited) understanding of the purpose of a finite state automata: it can control what inputs an object responds to at a given time and change the response to those same inputs based on the object state which is determined by actions that have been executed on that object in the past.

Let’s look at the diagram above representing a stop light. We’ll start at the red light (S1). In this example the traffic light can receive only input from the timer. Any input from the timer to the light less than 20 fails to satify the condition required for the light to transition from red to green so the light will remain red. A timer input == 20 causes the traffic light to transition. The transition from red to green executes an action to reset (exit action of red state) and start the timer (entry action of green state). The timer again send inputs to the traffic light. This time the traffic light will not respond until the timer input == 15, at which point the light will transition from green to yellow and once again reset and start the timer. The timer inputs now do not satisfy the conditions to transition until until the timer input == 5 which triggers a transition to our start point of the red light and yet again resets and starts the timer.

So Here Is My Attempt At Another Simplified Example

We have an imaginary car with an imaginary transmission. It is a four speed transmission with a neutral gear (If you want to parallel park this imaginary car go ahead, hop out and push it. Imagination doesn’t weigh much.) which means the transmission can be in one of five possible states.

[:neutral, :first, :second, :third, :fourth] - “What are all the distinct states of the system?”

The driver can give the transmission inputs to shift_up or shift_down and the transmission will behave just as you would expect. 1st gear can accept an input to shift up or shift down. So can second and third.

The ends are where it gets a bit more interesting. The tranmission will respond to an input to shift_up but it will not respond to an input to shift_down when it is in a :neutral state. Similarly, when the transmisson is in a state of :fourth it will only respond to an input of shift_down; shift_up will have no effect. This answers the question “To what stimuli will the system respond in a given state?”

So, no entry or exit actions, only one input (binary +/-) but I think it qualifies as a simple state machine.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

  class TransmissionStateMachine
    attr_reader :state

    TransmissonStates = [:neutral, :first, :second, :third, :fourth]

    def initialize
      @state = :neutral
    end

    def shift_up
      if state != :fourth
        idx = TransmissonStates.index(state)
        @state = TransmissonStates[idx + 1]
        puts "Shifted up to #{state} gear!"
      else
        puts "You're in top gear dummy!"
      end
    end

    def shift_down
      if state != :neutral
        idx = TransmissonStates.index(state)
        @state = TransmissonStates[idx - 1]
        puts "Shifted down to #{state} gear!"
      else
        puts "I can't go any lower down!  Is there a negative 1 gear?!?"
      end
    end

  end

  t = TransmissionStateMachine.new

  puts "Ready to go!"

  t.shift_up #Shifted up to first gear!
  t.shift_up #Shifted up to second gear!
  t.shift_up #Shifted up to third gear!
  t.shift_up #Shifted up to fourth gear!
  t.shift_up #You're in top gear dummy!
  t.shift_down #Shifted down to third gear!
  t.shift_down #Shifted down to second gear!
  t.shift_down #Shifted down to first gear!
  t.shift_down #Shifted down to neutral gear!
  t.shift_down #I can't go any lower down!  Is there a negative 1 gear?!?

So where are finite state machines used?

- A compiled regexp is a finite state machine.

- Network protocols which are state based like TCP.

- Lexical analyzer or token parser: It uses FSM to parse tokens into keywords or identifiers which are further used by the compiler.

- Vending machines.

- Video game AI.

- CPU controllers.

Sources:

Finite State Machines Explained- Video Finite State Machines- A Short Explanation How To Design A Finite State Machine State Machines in Ruby by Dave Kennedy State Machine Gem Finite State Machine Applications