How to store a complex state machine

Question

I have a rather complex state machine that I need to implement in Python. Everything I have tried so far has been very messy with a million loops and if statements. I have around 100 nodes, and every node can have multiple incoming and outgoing arcs.

Firstly, I already have the design of the state machine, it is not something that needs to be learned. Secondly, I don't want to use any packages like scikit-learn. Obviously, pandas and numpy are fine, but I want to sketch this up in Python and then bring it into C#, so it can't be too dependent on Python packages.

I have also tried using a graph, but it doesn't feel right because there are cycles, and the traversal algorithm is dependent on decisions, not costs. I was also thinking about writing a Domain Specific Language, but before I invest a lot of time into that, I want to make sure I have done some research.

What is the typical datastructure used to store a state machine? It needs to be able to account for cycles and sinks. Is a DSL the way to go? If so, do you have any pointers?

Thanks!

p.s it would look something like this.

Source: Figures - uploaded by Alex Capaldi from referenced research An AgentBased Modeling Approach to Determine Winter Survival Rates of American Robins and Eastern Bluebirds

Answer 1

The simplest representation of a statemachine is as a graph.

In most languages, you can use an array whose indices represent states, and whose elements are list of transitions to other states. It is often convenient to associate a human-readable state name with each index to support debugging. Transitions need two parts: a transition condition and a target statenumber.

We design an "internal" DSL in python by naming the graph constructors and elements we need. We can define a state machine (forgive my Python, I'm not an expert):

   Class Transition  // defines a single transition
      def __init__(self, condition, target):
        self.condition = condition // store a python lambda here
        self.target = target // may be a state name (optimize to a state index)

   Class State
      def __init__(self, state_name, transitions):
        self.state_name=state_name   // text name of state
        self.transitions=transitions // a "set" (array) of transitions

   Class StateMachine:
      def __init__(self, states):
        self.states = states  // a "set" (array) of named states
      def AddState(self, state):
        self.states.append(state) 
      def compile(self):
        // replaces state names with state indexes; left as reader exercise

We can construct a statemachine to recognize typical identifier name (same as regexp "[A-Z][A-Z0-9]*"):

    MyIdentifierRecognizer = StateMachine([])
    MyIdentifierRecognizer.AddState(State("ScanFirstIdentifierCharacter",
          [Transition(lambda x: IsLetter(x),"ScanNthIdentifierCharacter"),
           Transition(lambda x: not(IsLetter(x)),"NotAnIdentifier)]))
    MyIdentifierRecognizer.AddState(State("ScanNthIdentifierCharacter",
          [Transition(lambda x: IsLetterOrDigit(x),"ScanNthIdentifierCharacter"),
           Transition(lambda x: not(IsLetterOrDigit(x)),"EndOfValidIdentifier)])) 
    MyIdentifierRecognizer.AddState(State("NotAnIdentifier",[])) // no further transitions posssible
    MyIdentifierRecognizer.AddState(State("EndOfValidIdentifier",[])) // no further transitions possible

Running the state machine is easy. We first set up a current_state to the initial state of the state machine:

     current_state = "ScanFirstIdentifierCharacter"

then given an input character:

     character = ...

we locate the current_state in the state machine, and then process the transitions looking for one that is satisfied to change current_state:

     for s in StateMachine.states   // find the actual state matching current_state
         if s.name == current_state
            state = s
            break
     for t in state.transitions // process all transitions (assumed mutually exclusive)
          if t.condition(character)
             current_state=t.target
             break  // adding this line means "take the first valid transition"

You can make this more efficient by running a little "compiler" after defining the state machine, that replaces textual state names with array indexes. Then the state lookup can be a direct array index.

If interpreting this state machine isn't fast enough, you can compile the individual states to their equivalent target language code and import that code. Done properly, this will actually produce very fast state machines.

[Note: author added an example flowchart to his question after I completed this answer. I leave it to him to convert his flowchart in this state machine notation].

One other consideration motivated by OP's original question related to decision trees: how are the transition predicates stored? In my version here, they are "opaque" Python lambdas and that will satisfy some needs. If OP wants to store complex transition predicates in a non-opaque way, he'll need the "transition" field to contain an abstract syntax tree representing the boolean condition of interest. Details on how to parse (boolean) and execute boolean expressions can be found at https://stackoverflow.com/a/2336769/120163