Differences between revisions 7 and 17 (spanning 10 versions)
Revision 7 as of 2009-10-22 19:54:34
Size: 4054
Editor: s235-138
Comment:
Revision 17 as of 2014-09-06 09:12:52
Size: 5748
Comment: add tulip entry
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
This is a summary of FSM implementations in Python right now. <<TableOfContents>>

== Introduction ==

This is a summary of FSM implementations in Python right now. Licensing
remains unclear.
Line 8: Line 13:
<<TableOfContents>> == Finite State Machine Editor ==
Line 10: Line 15:
'''[[http://fsme.sourceforge.net/|Finite State Machine Editor]]''' [[http://fsme.sourceforge.net/|FSME]] 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.
Line 12: Line 19:
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.)
Line 14: Line 22:
Requires QT for the editor. (Not the compiler, though, which probably reads XML.)  * [[http://fsme.sourceforge.net/doc/tutorial.html|tutorial]]
 * [[http://fsme.sourceforge.net/phpwiki/|project wiki]]
Line 16: Line 25:
* [[http://fsme.sourceforge.net/doc/tutorial.html|tutorial]]
* [[http://fsme.sourceforge.net/phpwiki/|project wiki]]
== Tulip (Temporal Logic Planning Toolbox) ==
Line 19: Line 27:
[[http://tulip-control.sourceforge.net/|tulip]] includes a subpackage called [[https://github.com/tulip-control/tulip-control/tree/master/tulip/transys|transys]] that provides classes for (finite state)
Line 20: Line 29:
'''[[http://osteele.com/software/python/fsa/|FSA - Finite State Automation in Python]]'''   1. Transition systems ([[https://en.wikipedia.org/wiki/Kripke_structure_%28model_checking%29|Kripke Structures]], also known as generators of languages):
    * for closed systems
    * for open systems (that play against adversarial environments)
    
  The above support edge labeling, as well as state labeling (in that respect they are not pure Kripke structures and can be used to construct Labeled-transition systems, depending on the semantics assigned to the graph).
  
  2. [[https://en.wikipedia.org/wiki/Automata_theory|Automata]] (also known as acceptors):
    1. Finite-word:
      * [[https://en.wikipedia.org/wiki/Deterministic_finite_automaton|Deterministic Finite Automata]] (DFA)
      * [[https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton|Non-Deterministic Finite Automata]] (NFA)
    
    2. [[https://en.wikipedia.org/wiki/%CE%A9-automaton|Infinite-word]] (= ω-automata):
      * [[https://en.wikipedia.org/wiki/B%C3%BCchi_automaton|Buchi Automata]] (BA)
      * Rabin Automata (RA)
      * Parity Automata
  
  3. [[https://en.wikipedia.org/wiki/Finite_state_transducer|Machines]] (also known as transducers):
    * [[https://en.wikipedia.org/wiki/Mealy_machine|Mealy machines]]
    * [[https://en.wikipedia.org/wiki/Moore_machine|Moore machines]]
Line 22: Line 49:
This seems to be all about '''making''' FSMs, but I don't see a whole lot on how to ''use'' them! The toolbox includes an extension of [[http://networkx.github.io/documentation/networkx-1.9/reference/classes.multidigraph.html?highlight=multidigraph#networkx.MultiDiGraph|networkx.MultiDiGraph]] to define typed labeling and also a subpackage for exporting the above classes to:
Line 24: Line 51:
  * [[https://en.wikipedia.org/wiki/DOT_%28graph_description_language%29|GraphViz dot]] (inluding: TikZ (LaTeX), ipython qtconsole inline plot support of graphviz output)
  * [[https://en.wikipedia.org/wiki/Promela|Promela]] (for transition systems only)
  * [[https://en.wikipedia.org/wiki/D3.js|d3]]
Line 25: Line 55:
'''[[http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/146262|Noah Spurrier's FSM]]''' The implemented algorithms include the synchronous product between transition systems and Buchi automata.
Line 27: Line 57:
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. Tulip itself is a package for synthesizing correct-by-construction systems from a logic specification and a model expressed as a transition system, including - among other - functions for abstracting the continuous dynamics of systems governed by differential equations to finite state transition systems.
Line 29: Line 59:
You can also [[http://www.noah.org/python/FSM/|find it on his website.]] == FSA - Finite State Automation in Python ==
Line 31: Line 61:
[[http://osteele.com/software/python/fsa/|FSA]] seems to be all about
creating finite state machines, but I don't see a whole lot on how to use
them.
Line 32: Line 65:
'''[[http://www.research.att.com/projects/mohri/fsm/doc4/fsmpy.html|fsmpy module]]''' == Noah Spurrier's FSM ==
Line 34: Line 67:
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. http://www.noah.org/python/FSM/
Line 36: Line 69:
Noah's implementation is pure Python code. You init an FSM, register
transitions, and then throw inputs at it. States and inputs must be
hashable.
Line 37: Line 73:
'''[[http://wiki.python.org/moin/PythonDecoratorLibrary/|Decorator based FSM]]''' It's fairly similar to Skip's implementation (below).
Line 39: Line 75:
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. == fsmpy ==
Line 41: Line 77:
[[http://www.research.att.com/projects/mohri/fsm/doc4/fsmpy.html|fsmpy module]]
Line 42: Line 79:
'''SkipMontanaro's 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 44: Line 84:
[[http://www.python.org/search/hypermail/python-recent/0667.html|From an e-mail.]] == Decorator-based FSM ==

An [[http://wiki.python.org/moin/State Machine via Decorators|example using decorators]] is in the Decorator Library on this site. The module simplifies
implementation 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.

== Skip Montanaro's FSM ==

[[http://www.smontanaro.net/python/fsm.py|fsm.py.]]
Line 48: Line 98:
I've re-interpreted the code, adding formatting lost in e-mail, and PythonStyle-itizing it a bit. == python-fsm FSM module with PyGraphViz support ==
Line 50: Line 100:
{{{
#!python
"""Finite state machine, featuring transition actions."""
An concise yet comprehensive implementation based on Wikipedia spec of Finite State Machines. The module can be used to build and further describe finite state automata with DOT graphs. It implements acceptors and transducers (Moore and Mealy machines) and provides an straight-forward way to inject and execute state change actions for entry, exit, input and transition.
Line 54: Line 102:
FSMError = 'Invalid input to finite state machine' Licensed under the new BSD license.
Line 56: Line 104:
class FSM: [[http://code.google.com/p/python-fsm/]]
Line 58: Line 106:
    """Finite state machine, featuring transition actions. == fysom ==
Line 60: Line 108:
    The class stores a dictionary of (state, input) keys,
    and (state, action) values.
A port of Jake Gordon's [[https://github.com/jakesgordon/javascript-state-machine|javascript-state-machine]]. The module lets the user define callbacks for before/after events as well as callbacks on entering/leaving states. Events are exposed as object methods which when called, causes the appropriate state transition. The module also provides asynchronous callback functionality which allows delaying a state transition.
Line 63: Line 110:
    When a (state, input) search is performed:
    * an exact match is checked first,
    * (state, None) is checked next.

    The action is of the following form:
    * function(current_state, input)
    """
    
    def __init__(self):
        self.states = {}
        self.state = None
        self.dbg = None

    def add(self, state, input, newstate, action):
        """Add a transition to the FSM."""
        self.states[(state, input)] = (newstate, action)

    def execute(self, input):
        """Perform a transition and execute action."""
        si = (self.state, input)
        sn = (self.state, None)
        # exact state match?
        if si in self.states:
            newstate, action = self.states[si]
        # no, how about a None (catch-all) match?
        elif sn in self.states:
            newstate, action = self.states[sn]
        if self.dbg != None:
            self.dbg.write('State: %s / Input: %s /'
                           'Next State: %s / Action: %s\n' %
                           (self.state, input, newstate, action))
        apply(action, (self.state, input))
        self.state = newstate

    def start(self, state):
        """Define the start state.

        Actually, this just resets the current state.
        """
        self.state = state

    def debug(self, out):
        """Assign a writable file to log transitions."""
        self.dbg = out
}}}
[[https://github.com/oxplot/fysom]]

Introduction

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

For general information about finite state machines, see:

Finite State Machine Editor

FSME 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.)

Tulip (Temporal Logic Planning Toolbox)

tulip includes a subpackage called transys that provides classes for (finite state)

  1. Transition systems (Kripke Structures, also known as generators of languages):

    • for closed systems
    • for open systems (that play against adversarial environments)
    The above support edge labeling, as well as state labeling (in that respect they are not pure Kripke structures and can be used to construct Labeled-transition systems, depending on the semantics assigned to the graph).
  2. Automata (also known as acceptors):

    1. Finite-word:
    2. Infinite-word (= ω-automata):

  3. Machines (also known as transducers):

The toolbox includes an extension of networkx.MultiDiGraph to define typed labeling and also a subpackage for exporting the above classes to:

  • GraphViz dot (inluding: TikZ (LaTeX), ipython qtconsole inline plot support of graphviz output)

  • Promela (for transition systems only)

  • d3

The implemented algorithms include the synchronous product between transition systems and Buchi automata.

Tulip itself is a package for synthesizing correct-by-construction systems from a logic specification and a model expressed as a transition system, including - among other - functions for abstracting the continuous dynamics of systems governed by differential equations to finite state transition systems.

FSA - Finite State Automation in Python

FSA seems to be all about creating finite state machines, but I don't see a whole lot on how to use them.

Noah Spurrier's FSM

http://www.noah.org/python/FSM/

Noah's implementation is pure Python code. You init an FSM, register transitions, and then throw inputs at it. States and inputs must be hashable.

It's fairly similar to Skip's implementation (below).

fsmpy

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

An example using decorators is in the Decorator Library on this site. The module simplifies implementation 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.

Skip Montanaro's FSM

fsm.py.

Features transition actions.

python-fsm FSM module with PyGraphViz support

An concise yet comprehensive implementation based on Wikipedia spec of Finite State Machines. The module can be used to build and further describe finite state automata with DOT graphs. It implements acceptors and transducers (Moore and Mealy machines) and provides an straight-forward way to inject and execute state change actions for entry, exit, input and transition.

Licensed under the new BSD license.

http://code.google.com/p/python-fsm/

fysom

A port of Jake Gordon's javascript-state-machine. The module lets the user define callbacks for before/after events as well as callbacks on entering/leaving states. Events are exposed as object methods which when called, causes the appropriate state transition. The module also provides asynchronous callback functionality which allows delaying a state transition.

https://github.com/oxplot/fysom

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

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