View source

__FORCETOC__

== Finite State Machines Defined ==

* Six components
** an input alphabet (a set of input events)
** an  output alphabet (a set of output events)
** a finite set of states
** an initial state
** a state transition function that maps an input event and current state into the next state
** a function that similarly maps an input event and current state into the output
*** A "Mealy Automaton" associates the output with the transition (and time)
*** A "Moore Automaton" associates the output with the new state
* A deterministic FSM has only transition for each state/input combination
* A non deterministic FSM has multiple transitions for each state/input combination
** each transition has an associated probability
** the sum of the probabilities for each state/input combination is 1


{{SingleImage|imageWidthPlusTen=588|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/fsm/01.jpg|caption=Finite State Machine. State / Output shown in circles.}}



{{SingleImage|imageWidthPlusTen=588|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/fsm/02.jpg|caption=Finite State Machine. State / Output shown in circles.}}



{{SingleImage|imageWidthPlusTen=588|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/fsm/03.jpg|caption=Finite State Machine. State / Output shown in circles.}}



{{SingleImage|imageWidthPlusTen=588|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/fsm/04.jpg|caption=Finite State Machine. State / Output shown in circles.}}


{{SingleImage|imageWidthPlusTen=579|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/fsm/05.jpg|caption=Simple and complex Finite State Machines.}}



{{SingleImage|imageWidthPlusTen=579|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/fsm/06.jpg|caption=Simple and complex Finite State Machines.}}



{{SingleImage|imageWidthPlusTen=629|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/fsm/07.jpg|caption=Simple and complex Finite State Machines.}}



{{SingleImage|imageWidthPlusTen=629|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/fsm/08.jpg|caption=Simple and complex Finite State Machines.}}

== Markov Chains ==
A more general generative system than FSM, but similar in many ways, however...
* transitions are a function of one or more previous states as well as a probability
* can be created based on a statistical analysis of a real world situation
* i.e. textual synthesis based on reading and extracting statistics from known texts


{{SingleImage|imageWidthPlusTen=476|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/fsm/09.jpg|caption=Markov Synthesis.}}

== Pragmatics ==
* Strictly speaking FSM's do nothing without input, so how can they be used to generate?
** feed the FSM random input
** seed the FSM with a single value, and then feedback the input to the output
** have multiple FSM's and then cross couple their inputs and outputs
* Feedback and coupling require that the output and input alphabets be the same
* Speculative applications
** random input FSM - music composition
*** can random input be mapped into coherent music via a clever FSM?
** feedback FSM - mapping output into painting gestures
** coupled FSM's - dancers interacting