''Page by'' [Theo Verelst]

The mathematical model for a Finite State Machine is a mapping where

 from (Din,Dstate) |--> to (Rout,Rstate)
 FSM(in,state) --> (out,new state)

schematically the machine applies the mapping like:

           |----|
  in    -->|    |--> out
           |    |
  state -->|    |--> next state
           |----|

Or machinewise 


  clock ------    or 'trigger new state'
             |
             V
           |----|
  in    -->|    |--> out
           |    |
  state -->|    |--> next state
        |  |----| |
        |         |
        -<---------

The mappings from (in,state) to out and another to next_state are functions acting on domains which are respectively all possible inputs and all states (possibly minus the first or last), and which have ranges of all possible output values and all possible new state values.

From straigtforward reasoning one may take it that it holds that

 Domain(state) is subset of Range(newstate) minus newstate(initial)
''Surely you rather meant to write''
 Dstate is superset of Rstate union initial_states
''or something to that effect? - [Lars H]''

{Lets see, the domain of the variable state is a subset (or equal to) of the Range for newstate (because the last state need not be in the domain of the newstate function), except that the initial state need not be in the range for newstate. Maybe nicer put, the domain for the variable state and range for the function newstate are the same except not necessarily for the initial state and the final state}

and it makes most sense practically to take

 Domain(state) equals range Range(newstate) except for state(inital) and state(final)

The sequence of states which are traversed by starting from a given input and initial state is predictable and known when the model is no ill-defined. It can be a repeating sequence, or, by a changing input, infinite sequence without repetition, for instance by taking as states range and domain the decimal numbers 0 to 9 mapped to the some random output and a newstate equal to the previous input, and feeding the input with the decimals of PI.

See also [eigenvalues and electronics] and [bwise applications and examples] for an example on what logical functions can act as building block for remembering the state, this page has the same block and the bwise code: 

 http://195.241.128.75//Diary/ldiary6.html#bwise

This page is an example of how many bytes of source code [Finite State Machines] can be used to encode the number of states which often would fit in a byte, and the  transitions could probably be coded pretty shortly as well. Then again, an assembly program is usually much bigger than the resulting object code.

I think after rereading the math notation is not all clear though things are overseeable, the first def line above means that the machine is defined by a function mapping of two variables to two new variables with certain domains and ranges. Actually the functions have ranges, they don't need variables added to hold the values, as in normal math. In fact, the only variable which is not a function argument is the state variable, which needs to be given an initial value. Though it is mathematically possible to define the machine as deriving its first 'stored' state from the initial input, or to define the state only after a cycle of the machine.

----
In the past I made a page with a special extension of the finita state machine concept, which you can try out on the web page through a javascript ''live'' animation: 

   http://195.241.128.75/Tripod/Diary/diary62.html#machine

----
Of course on the tcl/tk wiki, one would at least have to give some code to make clear what a finite state machine can be made to tick like in tcl.

The following code makes the nextstate function by setting a array with a list of state, nextstate tuples, like a lookup table, initialized the state variable, and runs over some states. Next should be to include input, and then output. This of course is like a little program, easy enough, though quite fundamental, and interesting enough in terms of the possible traces, depending on the statespace, or domain and range of the nextstate function and the initial state. Ask dice players wether that is important.

 array set nextstate {{} 1 1 2 2 3 3 inf}
 proc compute_nextstate {oldstate} {
    global nextstate; 
    puts "state $oldstate --> [set newstate $nextstate($oldstate)]"; 
    return $newstate
 }
 compute_nextstate [compute_nextstate [compute_nextstate [compute_nextstate {}]]]

this gives:

 state  --> 1
 state 1 --> 2
 state 2 --> 3
 state 3 --> inf

Interesting for programmers here is of course is that we have an implicit state variable, the return value of the compute_nextstate function and the initial literal state value.

To list the State Transition Table in a listbox easily (assuming space in the tk toplevel . window):

 pack [listbox .lb]
 foreach {i j} [array get nextstate] {.lb insert end [list $i $j] }

----
[Category Concept]