Finite state machines
A finite state machine is an abstraction of the way a machine responds to external events. The machine can be in one of a finite number of states and can move between states when triggered by an external event or timer.
The finite state machine below models a coin oerated turnstyle on a public toilet. It can either be in the state of locked or unlocked. If you push on the gate when it is locked it remains in the locked state. If you insert
a coin then it changes from the locked state to the unlocked state. Adding more coins will not change its state. When the bar is pushed in the unlocked state it opens giving the person access to the toilet and returning to the
locked state.
Parts of a finite state machine
States: States are positions our machine can be in. They are generally labelled in shorthand e.g. S1 for state 1.
Start state: where we begin in our FSM. This is shown by the only arrow entering the machine from outside.
Accept state: If tracing the value of an input ends in an accept state then the input is valid.
Transitions: Show how we move between states. The reason to move is written on the arrow which shows the direction of the transition.
State transition tables
State transition tables are another way of representing a finite state machine. A state transition table shows for each state the resulting state of any given input. The state transition table below matches the finite state
machine drawn above.
Using a finite state machine
Consider the binary number 1010:
We start in the start state S1. The first digit is a 1 so we remain in S1. The next digit is a 0 so we move to S2. The next and digit is a 1 so we remain in S2. The next and final digit is a 0 so we return S1. As this
is an accept state the value 1010 is valid.
Consider the binary number 1101:
We start in the start state S1. The first digit is a 1 so we remain in S1. The next digit is a 1 so again we remain in S1. The next digit is a 0 so we move to S2. The next and final digit is a 1 so we remain in S2. As this
is not an accept state the value 1101 is invalid.