# A-level Computing 2009/AQA/Problem Solving, Programming, Data Representation and Practical Exercise/Problem Solving/Finite state machines

A finite state machine consists of states, inputs and outputs. The number of states is fixed; when an input is executed, the state is changed and an output is possibly produced. Finite state machines are widely used when designing computer programs, but also have their uses in engineering, biology, linguistics and other sciences thanks to their ability to recognise sequences.
A finite state machine expressed visually is a State transition diagram. It is used to show all the states, inputs and outputs. Each state is represented with a circle, and each transition with an arrow. Transitions are labelled with an input that causes a transition and possibly an output that results from it. A double circle signifies the accept state. Not all FSMs will have an accepting state and it is possible they could run forever.
A finite state machine can be with or without outputs:

## Finite state automaton

Looking at the above diagram we can see that it starts in state S1, an input of 1 will keep it in state one, and an input of 0 will move it to state S2. Once in S2 an input of 1 will keep it there, and an input of 0 will switch it back to S1. This means that the following inputs are valid:
It might appear to accept any binary value, but this isn't true. The only state it can accept in is state S1. This places the following rule on all accepted inputs: "A combination of binary digits involving an even number of zeros". This is useful for parity checks. If I try the following:
I am stuck in state S2 and the FSM has not accepted. Can you create a FSM to only accept Binary numbers with odd numbers of 1s?
* Exercise: Finite State Automaton
* For the FSM above which of these inputs are valid:
* aaacdb
* ababacdaaac
* abcdb
* acda
* acdbdb
* Answer:
* aaacdb (CORRECT)
* ababacdaaac(CORRECT)
* abcdb (ERROR no input that accepts b then c)
* acda (ERROR S1 is not a accepting state)
* acdbdb (CORRECT)
* For the FSM above which of these inputs are valid:
* 987654321+994-0
* 5-5+2*4
* 9+8+7+6+5+4+3+2+1
* 0+1+2+1+
* 99+88-77
* Answer:
* 987654321+994-0 (CORRECT)
* 5-5+2*4 (ERROR no input *)
* 9+8+7+6+5+4+3+2+1 (CORRECT)
* 0+1+2+1+ (ERROR S3 is not a accepting state)
* 99+88-77 (CORRECT)
* Draw a finite state automata that will accept the word Banana whilst using only 3 states
* Answer:
* Draw a finite state automata that will accept the words:
* Tim
* Grit
* Grrrrrim
* Answer:

## Mealy Machines

Some FSMs output values dependent on the state and the input values:
The above Mealy Machine outputs a value for each input. You can tell which is which by: input / output. So for the following input:
It outputs
Shifting all the bits right, and dividing the binary number input by two.
* Exercise: Mealy Machines
* For the Mealy machine above, what do the following inputs output:
* 50
* 20,10,20
* 10,10,10,20
* What does this machine do, what do the outputs tell you?
* Answer:
* 0
* 30,20,0
* 40,30,20,0
* This machine could be used to track the money going into a vending machine, letting you know how much you have left to pay on a 50p chocolate bar
* What is the difference between a mealy machine and a finite state automaton?
* Answer:
* mealy machines output values
* finite state automata do not
* Extension: non-determinism
* In this section we are learning about deterministic finite automaton. This means that for a state and a valid input there is only one possible transition to take. There are such things a nondeterministic finite automaton where, for a given input there are multiple paths (or none) that could be taken:
* In state p, for input 1 there are two possible transitions

### State transition tables

A state transition table follows every state and input. Inputs are usually placed on the left, and separated from the outputs, which are on the right. Here's a simple example of a state machine with two states, and a binary input:
| Input | Current State | Next State | Output |
| 0 | S$_1$ | S$_2$ | null |
| 1 | S$_1$ | S$_1$ | null |
| 0 | S$_2$ | S$_1$ | null |
| 1 | S$_2$ | S$_3$ | null |
Exercise: State transition tables
Create a state transition table for the following FSM:
Answer:
InputCurrent StateNext StateOutput
0S$_1$S$_2$null
1S$_1$S$_1$null
0S$_2$S$_1$null
1S$_2$S$_2$null
Create a state transition table for the following FSM:
Answer:
InputCurrent StateNext StateOutput
0S$_0$S$_2$0
1S$_0$S$_1$0
0S$_1$S$_2$1
1S$_1$S$_1$1
0S$_2$S$_2$0
1S$_2$S$_1$0
Draw the FSM for the following state transition table:
InputCurrent StateNext StateOutput
TimerGreenGreennull
ButtonGreenYellownull
TimerYellowRednull
TimerRedGreennull
Answer:
You might have already cottoned on. This represents a traffic light system
Draw the FSM for the following state transition table:
InputCurrent StateNext StateOutput
aq0q0null
bq0q1null
aq1q2null
bq1q1null
aq2q1null
bq2q1null
Answer: :