Finite State Machine

aka State Machine

definition - A model of computation consisting of a set of states, a start state, an input alphabet, and a transition function that maps input symbols and current states to a next state.

http://www.c3.lanl.gov/mega-math/gloss/pattern/dfa.html

http://en.wikipedia.org/wiki/Finite_state_machine

States are mutually exclusive in the case of a deterministic state machine. And this is what's usually used for modeling software and user interface components.

  • though when I try to think of things this way I see so many dimensions each with multiple possible values that the combinatorial explosion of states drives me nuts

Python Cookbook entry on using a Finite State Machine for parsing.

PyF S A http://osteele.com/software/python/fsa/

State MachineCompiler project looks interesting. The "compiler" runs on Java but generates classes for a number of other languages (including Python) (but the Java is always running on your Roll Out machine).

  • Bob Martin (Robert Martin) started SMC around 1991. I picked it up the same year. My experience up to then had been with formal Finite State Machines (FSM), Push-down FSM and with something called an Augmented Transition Network (ATN) which is an FSM on steriods. ATNs were used in Natural Language Processing to parse text (used mostly in the 1970s). ATNs have transition guards, push/pop transitions, default transitions and backtracking (rewind state transitions to an earlier time and try a different transition - needed in parsing text but not possible in Event Driven software unless you have a time machine.) If your are familiar with ATNs, you can see where SMC came from. I have tried to use UML syntax wherever possible. But there is no getting around that my philosophy about state machines is distinct from the Harel/UML philosophy.

  • It also [generates](http://smc.sourceforge.net/Smc Faq.htm#Table) HTML tables and GraphViz graphs as output of your state tables.

  • Documentation [on](http://smc.sourceforge.net/Smc Man Sec1.htm) writing the .sm state file.


Edited: |

blog comments powered by Disqus