Finite state machines

See also Finite State Machine

Arjen Markus: They are very powerful programming devices, but most languages are unsuitable to actually define them: (finite) state machines. Everyday examples: parsers in Yacc/Lex, regular expressions, protocol handlers and so on.

Below is a small script, inspired by a paper on Forth, that shows that Tcl can retain the table-like appearance that one so dearly loves, when specifying a state machine. (Okay, it does little or no error checking, it defines only deterministic finite state machines, and the example is overly simple, but still, have a look).

# statemachine.tcl --
#
#    Script to implement a finite state machine
#
# Version information:
#    version 0.1: initial implementation, april 2002


namespace eval ::FiniteState {
    variable statemachine

    namespace export defineMachine evalMachine resetMachine
}

# defineMachine --
#    Define a finite state machine and its transitions
#
# Arguments:
#    machine      Name of the machine (a variable)
#    states       List of states
#
# Result:
#    None
#
# Side effects:
#    The variable "machine" is filled with the definition
#
# Notes:
#    The list of states can only contain the commands initialState
#    and state. No others are allowed (no check though)
#
#    For instance:
#    defineMachine aMachine {
#       initialState 1
#       state 1 {
#          "A" 2 {puts "To state 2"}
#          "B" 3 {puts "To state 3"}
#       }
#       state 2 {
#          "C" 1 {puts "To state 1"}
#          "D" 3 {puts "To state 3"}
#       }
#       state 3 {
#          "E" 3 {exit}
#       }
#    }
#
#
proc ::FiniteState::defineMachine { machine states } {
    upvar $machine machinedef

    set machinedef {}
    set first_name {}
    set maxarg     [llength $states]
    for { set idx 0 } { $idx < $maxarg } { incr idx } {
        set arg [lindex $states $idx]
        switch -- $arg {
        "state" {
             set statename   [lindex $states [incr idx]]
             set transitions [lindex $states [incr idx]]
             lappend machinedef $statename $transitions
        }
        "initialState" {
             set first_state [lindex $states [incr idx]]
        }
        default {
        }
        }
    }

    #
    # First three items are reserved: the initial state and the current
    # state. By storing them in the same list we can pass the
    # information around in any way needed.
    #
    set machinedef [concat $first_state $first_state $machinedef]
}

# evalMachine --
#    Evaluate the input and go to the next state
#
# Arguments:
#    machine      Name of the machine (a variable)
#    input        The input to which to react
#
# Result:
#    None
#
# Side effects:
#    The machine's state is changed and the action belonging to the
#    transition is executed.
#
proc ::FiniteState::evalMachine { machine input } {
    upvar $machine machinedef

    set current_state [lindex  $machinedef 1]
    #
    # Look up the state's transitions
    #
    set states      [lrange $machinedef 2 end]
    set idx         [lsearch $states $current_state]
    set transitions [lindex  $states [incr idx]]

    set found 0
    foreach {pattern newstate action} $transitions {
        if { $pattern == $input } {
            uplevel $action
            set found 1
            break
        }
    }
    if { $found } {
        set machinedef [lreplace $machinedef 1 1 $newstate]
    } else {
        #error "Input ($input) not found for state $current_state"
        # Or rather: ignore
    }
}

# resetMachine --
#    Reset the machine's state
#
# Arguments:
#    machine      Name of the machine (a variable)
#
# Result:
#    None
#
# Side effects:
#    The machine's state is changed to the initial state.
#
proc ::FiniteState::resetMachine { machine } {
    upvar $machine machinedef

    set initial_state [lindex  $machinedef 0]
    set machinedef [lreplace $machinedef 1 1 $initial_state]
}

#
# Define a simple machine to test the code:
# A furnace that needs to keep the same temperature, so the heating
# may be on or off
#
namespace import ::FiniteState::*

defineMachine heater {
    initialState off
    state off {
        "too_cold" on  { set heating $heat_capacity}
    }
    state on {
        "too_hot"  off { set heating 0 }
    }
}

set time            0.0
set dt              0.1
set temp_amb       20.0
set temp           $temp_amb
set temp_ideal    200.0
set exch            0.3
set heating         0.0
set heat_capacity 500.0

while { $time < 10.0 } {
    evalMachine heater \
        [expr {$temp<=$temp_ideal? "too_cold" : "too_hot" }]

    set time [expr {$time+$dt}]
    set temp [expr {$temp+$dt*($exch*($temp_amb-$temp)+$heating)}]
    puts [format "%4.1f  %7.3f  %5.1f  %s" $time $temp $heating [lindex $heater 1]]
}

Theo Verelst (who put 'anonymous' here? I sure didn't.):

The formal definition of a finite state machine is that it has a countable number of (thus discrete) states, where it holds that the new state and output are computed from the old state with the inputs, which imo is relatively easy to program in any language:

set state on

proc newstate {input} {
    global state
    switch $state \
        off {return off} \
        on  {if [string match $input on] {set state on} {set state off} }
}

newstate on
puts $state
newstate off
puts $state

Though of course not at all always easy to analyse.

Lars H: The problem is seldom to encode the transition function, which is really all you did, but to use the finite state machine as a control structure. A goto command is in some sense the optimal (although not necessarily the most convenient) way to encode this, but in some languages that isn't easy to do. Also, your definition of a finite state machine is incorrect; countable allows the smallest infinite sets (such as that of the integers, or that of all finite words on a finite alphabet), but in a finite state machine the set of states must be (surprise?) finite.

Theo Verelst: Which goes to show you're not a computer designer, in hardware, there is no such thing as the goto or whatever it is which executes the what you call state transition, there is a mapping between the current and the next state, and how you achieve the implementation of that mapping could even be a ROM. Or of course and Arithmetic Logical Unit. Integers in Tcl and computers are always bounded by word size, though I'd easily agree that it is interesting mathematically to make them a list and let imagination take over.

A control structure. Hmm. The whole pentium or whatever CPU one uses, even when not a von Neuman, and possibly even when outside the broad turing machine boundaries, is full of logical circuits which can be interpreted as 'control structures', which form the basis of the functioning of the processor, the software control structure, living at a higher level of agregation but a very much lower level of actual control choices being made per second, can be made or seen as one wants on the basis of what conditionals or pointer like structures one may want to apply from the instruction set. In that respect it is no doubt of interest to include direct referencing (say like in traps) or some mathematical construct to arrive at some piece of code or a single instuction, in an easy, cheap and overseeable way. Or a lookup table. Or list referencing, which I consider pleasing.

The problem or limitation is that the FSM model is probably not the most natural to program in, and in its kind, which is suitable for message processing, it is limited, for isntance when faced with non determinate network problems, which it cannot formally resolve unambiguously or even define generally (like a petri net for instance). It is a design model which allows you to separate state and functions, and the idea is that the state is known, and usually limited, and therefore overseeable. And that every transition is between two well defined states at well defined time instances.

I guess it will be some time before our computers will have states which can cruise surfing Riemann surfaces somehow infinitely accurate.

I think countable means just that, I wouldn't say and integer number approaching infinity is countable, but I guess that is a matter of definition. Possibly even an interesting one.

AM: The mathematical definition of countable encompasses both finite and infinite sets. Discrete sets encompass both countable and incountable sets, as an example of the latter: consider the set obtained by removing all rational numbers from a finite-length interval of the real line. What you left with is a discrete, uncountable set. (I shamefully erased a remark about the Cantor set).

TV: 'Finite length interval' those words at least have a nice ring to it in the context..

AM: Quite intentional :)

TV 2003-11-18: Coming across this page because I do know where I'm going with fsm, process algebra and that in realm of software (and did so a decade ago at least, and about 3 decades ago about hardware, where the concept is commongood for the advanced), I can't agree to not making the remark that the above is like discussing the existence of distinquishable particles when pondering on the the existence of a Fock or Hilbert space. Appearently no expert speaking.

DKF: Two points

goto is merely an artefact of the process of flattening a state graph onto linear memory.
It should be possible to map between a Turing Machine and any other state machine representation that admits an infinite state space of sufficient complexity. I think the "sufficient complexity" bit refers to the requirement to be able to represent more than a single non-negative number of arbitrary magnitude.

TV: Well, I guess the second depends on how you define, or wish to stretch the definition of, a state machine.

You can take it that a possible state machine is a weight on a spring with a certain spring constant and weight, the input being gravity or the external force applied to the system, and the output being the displacement and velocity of the weight as function of time.

Perfectly neat little state machine, completely dead relevant to many branches of science, well definable, non a tricked construct, except it isn't a finite state machine: it has a continuous state of two variables, any two out of acceleration, velocity and discplacement (the other is differential/integral function derivable). Two continuous variables, possibly with bounded values, usually an infinite number of them, probably from R, though possibly only in Q.

A traffic light, not including the clock signal, that is the 'apply change' is an clear example of a finite state machine in normal definition. It runs through a prefixed trace of light changes each time it is activitated. The state variable would be something like

{red green red green}

For a 4-light variation, where clearly red, green and orange are the possible values of each substate, so that we have a total of 3^4

% expr int(pow(3,4)+0.5)
81

possible overall distinguishable (very countable and finite) states. The number of actually occuring states given the transition function, possibly regarding symmetry, is less, or lets say, the domain of the next-state function is more limited than that, because certain states are never reached in a legal and correct traffic light controller. To give this finite state machine, with rigid state transition timing scheme, inputs, one may have a reset button, 'request green' buttons or detection loops, and maybe a police-supervisor-override control input.

Two examples of state machines, one infinite, the other finite.

A computer in basic form as it is visible to a normal progammer is, apart from distinct deviations because of networks and hardware failures or special circuits, made in actual fact to act as a perfect state machine of the traffic light variation: with a limited number of states.

The states are countable, and the total number of them is the number formed by the possible combinations of all the bits stored in it, that is in the memory and the processor and add-ons normal and special registers. The hardware machinery acts as a complex but predictable state transition function on that state. For most current processors, that principle can even be found in actual practice where the chips can be tested with what is called JTAG, where all the bits of its state are serialized and can be read out and written to as a single (long) bitstring. State changes are applied by the hardware of the computer machinery, which compute the new state of all the memory bits (including the internal, possibly programmer invisible ones) from the old state of all memory bits at every tick of the hardware clock.

Taking this model as a starting point, and wanting to use state machine related reasoning on the running of compute programs leads to seeing a jump instuction, which is normally the low level basis for goto, as forcing a particular piece of the overall computer state, namely the program counter, in a new state, different from the slightly incremented normally expected new state.

I recall some pages on state machines:

Finite State Machine Main definitions.

Finite State Machine a tcl example indeed

Flip Flop to see why it is imperative to not tolerate the thinking that connecting functions together always yields a function, in this case, the joining of the two simples two variable functions which exist give a combined behaviour which actually has a state

mathematical foundation of computers and programs Might be good reading, it shows a page from the actual pentium datasheet

state of dutch politics machine is a dynamical or expanding state machine with sort of fun, probably useless, application.

UKo 2006-06-14: Just added a little bit of makeup to the output of the example.

AMG: I cleaned up some corrupted character encoding. I hope no one minds that I substituted in straight quotes to avoid future problems. TV accidentally used the encoding wrong back in November 2003, and things went downhill from there. Careful, guys...

The Rappture project includes a FSM program.

The Statenet package creates a finite-state network of linked states, specifically for use as a Hidden Markov Model for speech recognition. [1]

Building a Respirometer using FSM, Tcl and Arduino

See Also edit