Differences between revisions 5 and 6
Revision 5 as of 2007-03-28 22:48:33
Size: 4054
Editor: 64
Comment: Add link to Decorator based FSM
Revision 6 as of 2008-11-15 14:00:04
Size: 4066
Editor: localhost
Comment: converted to 1.6 markup
Deletions are marked like this. Additions are marked like this.
Line 5: Line 5:
 * [wiki:WikiPedia/Finite_state_machine Wikipedia:Finite_state_machine] -- B) ''excellent!'' B)
 * [wiki:Wiki/FiniteStateMachine Wiki:FiniteStateMachine]
 * [[WikiPedia:Finite_state_machine|Wikipedia:Finite_state_machine]] -- B) ''excellent!'' B)
 * [[Wiki:FiniteStateMachine|Wiki:FiniteStateMachine]]
Line 8: Line 8:
[[TableOfContents()]] <<TableOfContents>>
Line 10: Line 10:
'''[http://fsme.sourceforge.net/ Finite State Machine Editor]''' '''[[http://fsme.sourceforge.net/|Finite State Machine Editor]]'''
Line 16: Line 16:
* [http://fsme.sourceforge.net/doc/tutorial.html tutorial]
* [http://fsme.sourceforge.net/phpwiki/ project wiki]
* [[http://fsme.sourceforge.net/doc/tutorial.html|tutorial]]
* [[http://fsme.sourceforge.net/phpwiki/|project wiki]]
Line 20: Line 20:
'''[http://osteele.com/software/python/fsa/ FSA - Finite State Automation in Python]''' '''[[http://osteele.com/software/python/fsa/|FSA - Finite State Automation in Python]]'''
Line 25: Line 25:
'''[http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/146262 Noah Spurrier's FSM]''' '''[[http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/146262|Noah Spurrier's FSM]]'''
Line 29: Line 29:
You can also [http://www.noah.org/python/FSM/ find it on his website.] You can also [[http://www.noah.org/python/FSM/|find it on his website.]]
Line 32: Line 32:
'''[http://www.research.att.com/projects/mohri/fsm/doc4/fsmpy.html fsmpy module]''' '''[[http://www.research.att.com/projects/mohri/fsm/doc4/fsmpy.html|fsmpy module]]'''
Line 34: Line 34:
This seems to be a Python wrapper around [http://www.research.att.com/projects/mohri/fsm/ AT&T's FSM library.] It's all oriented around "weighted" finite state machines, so I'm not so sure how suitable it is if you just want to use unweighted FSM. This seems to be a Python wrapper around [[http://www.research.att.com/projects/mohri/fsm/|AT&T's FSM library.]] It's all oriented around "weighted" finite state machines, so I'm not so sure how suitable it is if you just want to use unweighted FSM.
Line 37: Line 37:
'''[http://wiki.python.org/moin/PythonDecoratorLibrary/ Decorator based FSM]''' '''[[http://wiki.python.org/moin/PythonDecoratorLibrary/|Decorator based FSM]]'''
Line 44: Line 44:
[http://www.python.org/search/hypermail/python-recent/0667.html From an e-mail.] [[http://www.python.org/search/hypermail/python-recent/0667.html|From an e-mail.]]

This is a summary of FSM implementations in Python right now.

For general information about finite state machines, see:

Contents

Finite State Machine Editor

This is a tool where you can draw FSM diagrams, and then compile to a Python module (or C++ code.) It also makes an XML description of the FSM.

Requires QT for the editor. (Not the compiler, though, which probably reads XML.)

* tutorial * project wiki

FSA - Finite State Automation in Python

This seems to be all about making FSMs, but I don't see a whole lot on how to use them!

Noah Spurrier's FSM

This is one found on ActiveState; It's purely Python code. You init an FSM, register transitions, and then throw inputs at it. States and inputs must be hashable.

You can also find it on his website.

fsmpy module

This seems to be a Python wrapper around AT&T's FSM library. It's all oriented around "weighted" finite state machines, so I'm not so sure how suitable it is if you just want to use unweighted FSM.

Decorator based FSM

A decorator based FSM can be found in the Decorator Library on this site. The module simplifies implementaion of FSM's based on UML 2.0 state diagrams. The FSM is implemented as a class, with methods of the class associated with transitions or with states. The design is not the best for constructing FSMs to parse text being somewhat slower than alternatives.

SkipMontanaro's FSM

From an e-mail.

Features transition actions.

I've re-interpreted the code, adding formatting lost in e-mail, and PythonStyle-itizing it a bit.

   1 """Finite state machine, featuring transition actions."""
   2 
   3 FSMError = 'Invalid input to finite state machine'
   4 
   5 class FSM:
   6 
   7     """Finite state machine, featuring transition actions.
   8 
   9     The class stores a dictionary of (state, input) keys,
  10     and (state, action) values.
  11 
  12     When a (state, input) search is performed:
  13     * an exact match is checked first,
  14     * (state, None) is checked next.
  15 
  16     The action is of the following form:
  17     * function(current_state, input)
  18     """
  19     
  20     def __init__(self):
  21         self.states = {}
  22         self.state = None
  23         self.dbg = None
  24 
  25     def add(self, state, input, newstate, action):
  26         """Add a transition to the FSM."""
  27         self.states[(state, input)] = (newstate, action)
  28 
  29     def execute(self, input):
  30         """Perform a transition and execute action."""
  31         si = (self.state, input)
  32         sn = (self.state, None)
  33         # exact state match?
  34         if self.states.has_key(si):
  35             newstate, action = self.states[si]
  36         # no, how about a None (catch-all) match?
  37         elif self.states.has_key(sn):
  38             newstate, action = self.states[sn]
  39         if self.dbg != None:
  40             self.dbg.write('State: %s / Input: %s /'
  41                            'Next State: %s / Action: %s\n' %
  42                            (self.state, input, newstate, action))
  43         apply(action, (self.state, input))
  44         self.state = newstate
  45 
  46     def start(self, state):
  47         """Define the start state.
  48 
  49         Actually, this just resets the current state.
  50         """
  51         self.state = state
  52 
  53     def debug(self, out):
  54         """Assign a writable file to log transitions."""
  55         self.dbg = out

FiniteStateMachine (last edited 2014-09-06 09:12:52 by IoannisFilippidis)

Unable to edit the page? See the FrontPage for instructions.