Finite State Machines

Finite State Machines refer to mechanise systems which may change between a pre-defined number of 'states', which refer to different situations, the most basic example being 'on' or 'off'.  These systems also contain inputs which cause a change between states, as well as possibly outputs.  If there are no outputs then the system will be known as a Finite State Automaton and have a 'goal' or 'accept' state.  They can be represented as state transition diagrams, as depicted below with arrows as transitions between states due to inputs.  In these diagrams there is an initial state denoted with a start arrow, and the accept state will be shown by a double circle.

Those Finite State Machines with outputs do have an initial state, but not an 'accept' state.  They are known as Mealy Machines.  A state transition diagram for a vending machine, an example of one, is shown below.

Transition tables can also be used for these systems and they differ depending upon whether the FSM has an output.  The first table is for the first FSM, whilst the second table is for the second FSM.

Input	Current State	Next State
Nothing	S0	S0
Incorrect Code	S0	S1
Nothing	S1	S0
Correct Code	S0	S2
Nothing	S2	S0

Input	Current State	Output	Next State
0p	S0	0	S0
50p	S0	0	S1
50p	S1	1	S2
£1	S0	1	S2
0p	S2	0	S1

Decision tables let one consider the possible combinations and what should happen as a result.
Example: if the week day is odd then output A, if it is even then output B

Conditions	Specific Data
Mon/Wed/Fri/Sun	Y	N
Tues/Thurs/Sat	N	Y
Output A	Y	N
Output B	N	Y

Y = Yes, N = No

Psuedo code can also used to represent these problems as they would be using similar syntax to inside a computer program, but not in a programming language.  For the example shown above the pseudo code would be something like:

If Day = Odd, then Output A
Else Output B