Welcome, guest | Sign In | My Account | Store | Cart

This may not be useful to many people, but this is a very simple finite state machine. It is defined as a class so that you can have multiple state machines running at the same time - all with different state/transition lists.

Python, 92 lines
 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#! /usr/bin/env python

""" Generic finite state machine class
    Initialise the class with a list of tuples - or by adding transitions
"""

class fss(object):
    def __init__(self, states=[]):
        self._states=states
        self.currentState = None

    def start(self,startState=None):
        """ Start the finite state machine
        """
        if not startState or not (startState in [x[0] for x in self._states]):
            raise ValueError("Not a valid start state")
        self.currentState = startState

    def stop(self):
        """ Stop the finite state machine
        """
        self.startState = None
    
    def addTransition(self,fromState, toState, testFunc):
        """ Add a state transition to the list, order is irellevant, loops are undetected 
            Can only add a transition if the state machine isn't started.
        """
        if not self.currentState:
            raise ValueError("StateMachine already Started - cannot add new transitions")

        # add a transition to the state table
        self._states.append( (fromState, toState,testFunc))

    def event(self, value):
        """ Trigger a transition - return a tuple (<new_state>, <changed>)
            Raise an exception if no valid transition exists.
            Callee needs to determine if the value should be consumed or re-used
        """
        if not self.currentState:
            raise ValueError("StateMachine not Started - cannot process event")

        # get a unique list of next states which are valid       
        self.nextState = list(set( \
                    [ x[1] for x in self._states\
                    if x[0] == self.currentState \
                            and (x[2]==True or (callable(x[2]) and x[2](value))) ] ) ) 

        if not self.nextState: 
            raise ValueError("No Transition defined from state {0} with value '{1}'".format(self.currentState, value))
        elif len(self.nextState) > 1:
            raise ValueError("Ambiguous transitions from state {0} with value '{1}' ->  New states defined {2}".format(self.currentState, value, self.nextState))
        else:
            self.currentState, ret = (self.nextState[0], True) \
                    if self.currentState != self.nextState[0] else (self.nextState[0], False)
            return self.currentState, ret

    def CurrentState(self):
        """ Return the current State of the finite State machine
        """
        return self.currentState

# Example code - showing populates of the state machine in the constructor
# the Machine could also be constructed by multiple calls to addTransition method
# Example code is a simple tokeniser 
# Machine transitions back to the Start state whenever the end of a token is detected

if __name__ == "__main__":
    fs = fss( [ ("Start","Start",lambda x: x.isspace() ),
                ("Start","Identifier",str.isalpha),
                ("Identifier","Identifier", str.isalnum),
                ("Identifier","Start",lambda x: not x.isalnum() ),
                ("Start","Operator", lambda x: x in "=+*/-()"),
                ("Operator","Start", True),
                ("Start","Number",str.isdigit),
                ("Number","Number",lambda x: x.isdigit() or x == "." ),
                ("Number","Start",lambda x: not x.isdigit() and x != "." ),
                ("Start","StartQuote",lambda x: x == "\'"),
                ("StartQuote","String", lambda x: x != "\'"),
                ("String","String",lambda x: x != "\'"),
                ("String","EndQuote", lambda x: x == "\'"),
                ("EndQuote","Start", True ) ] )

    fs.start("Start")

    a = "    x123=MyString+123.65-'hello'*value"
    c = 0 
    while c < len(a):
        ret = fs.event(a[c])
        print "{0}-> {1}".format(a[c], ret)
        # Make sure a transition back to start (from something else) does not consume the character.
        if ret[0] != "Start" or (ret[0] == "Start" and ret[1] == False):
            c += 1

http://en.wikipedia.org/wiki/Finite-state_machine

The Finite State Machine class keeps track of the current state, and the list of valid state transitions.

You define each transition by specifying :

  1. FromState - the starting state for this transition
  2. ToState - the end state for this transition
  3. testFunc - a callable which when it returns True means this transition is valid

There is no validation on these values, and it is perfectly legal to build a state transition where FromState and ToState are the same state, or to build a State machine with no end state.

The key part of the Finite State Machine is the "event" method - which takes a value (of any type), and tries to find a single valid transition in the defined transition list -i.e. one which has a FromState, and where the testFunc is invoked with the value as an argument will return True.

Generally testFunc is a callable - i.e. a predefined function or method, or as illustrated a lambda function. It is also possible to define testFunc for a transition as True (i.e. not a callable) - this is illustrated in the example code - in this case the transition always happens regardless of the value passed to the event method. Defining TestFunc in this way has it's uses - see in the EndQuote state in the exmaple.

The event method will raise an exception if there is no valid transition for the value provided, or if the value could result in more than one transition.

The event method returns a tuple containing the new state and an indication if the state has changed - again useful if you need to resubmit the same event.

There is some simple protection built into the machine - for instance you can't modify the machine once it has started.

By using data to define the Finite State Machine it avoids the need to hard code the details.