RR NDB, #2168
Would be useful to the thread to make a short briefing on "Finite State Machines", for me a fascinating issue.
Ok, will will give it a shot and apologies to those who find this
oversimplified or even patronising:
Long before the days of software programmed microcomputers, there was a
need to be able to manage fixed sequences of events or 'states'. For
example, repetitive industrial processes.
For a trivial and incomplete example, consider the industrial bottle
filling line below. The state column defines
valid states, while the
description defines
actions, or what happens for each of those states.
For each state, an action is performed and a decision made as to which
state to move (transition) to next.
State Action / Transition
----- -------------------
0 Move next bottle to fill position
1 Open valve to fill bottle
2 If bottle not full, hold at state 2, else, goto state 3
3 close valve
4 if more bottles, goto step 0, else goto step 5
5 end, process complete
The key things to note here is that each defined state is associated with
an action and that
only defined states are valid. Any other condition,
such as a broken or jammed bottle, is defined as an error. Errors may in
fact be handled by more states, after which the normal state sequence
would be restarted, but let's keep it simple. In the old days, such a
plant would have been implemented using electromechanical relays, pneumatics
and motors. To summarise then: The states, the action at each state and
transitions between states are designed to "encapsulate" the system functionality completely.
Finite state machines as we now understand the term were first (and are
still used) to implement complex digital logic functions in hardware.
If you like, programmed solutions for systems whare the the
sequence of
data being processed and it's
methods never change. They were widely used in
telecoms to decode and translate data streams between exchanges and
subscribers. Because of the speed limitations of early microcomputers,
such work could only be done in hardware, but later processors allow
this work to be done in software. In a way, it's still really all software
though, even when done in hardware
For a more cutrrent example, we have to digress a little to communications
protocols. You can think of a protocol as an agreed language between one
or more systems that need to talk to each other. Such a language will be
transported in messages between one system and another. For a
trivial example, the wire between your home computer and printer carries a
defined message protocol to allow the two to talk to each other.
Messages are typically split into sections that describe, for example,
the start a new message (ie: phone off hook), control information, (ie, what
the message means) the data itself (ie: engine speed value), provide
error detection and signal the end of the message (phone hangup). Messages
are typically sent sequentially in time. That is, the overall message
is sent sequentially, one section after another.
Because of the agreed protocol and if the receiving node is keeping track
of parts already received, it knows which part of the message is coming next.
It can thus decode what each part of the message means without ambiguity.
So how do we keep track of where we are in the message?. We know that the
message has several sections and we know from the protocol spec the order in
which they should be received. We can thus define states that correspond to
each section, the actions that need to be performed and the transition to
the state that processes the next section of the message.
From a software engineering point of view, state machine based design
is a powerfull technique that allows a problem to to be broken down into
a number of small, well defined steps and can simply the generation of
demonstrably deterministic systems. Arguably the most socially significant
example is the internet, where the tcp/ip network stack is a state machine
based design.
This is a long post and hope it's not overdone. There's loads of info on
the web about state machine design that should fill in the gaps, or can
post a bit more if needed...