Finite State Machines

- Finite means countable.
- A FSM is a machine that consists of a fixed set of possible states.
- These states can be - Allowable inputs that change the state
                                 - Outputs that change the state back to the original.
- The outputs only depend on the current state.
- The current state depends on the history of the sequence of inputs.
- Many types of digital machines are FSMs.
- Each state is one step towards the solution of the problem.
- Increasing the clock rate of a computer enables it to solve problems more quickly.

State Transition Diagrams
- A ballpoint pen is an example of an FSM.
- It has a finite number of states - Ballpoint extended
                                                - Ballpoint retracted
- It has a set number of allowable inputs - Clicking the pens button
- It has a set of outputs - retracting or extending the ballpoint
-In the diagram it has two states 1 and 0 and two transitions indicated by curved arrows
- State 1 is the ballpoint being exteneded and State 0 is the ballpoint being retracted

State Transition Tables
- We can use a table that shows the state that follows for every state and every input.
Table for ballpoint pen

- One reason FSMs are so useful is that they can recognise sequences.
- An FSM with no outputs is called a Finite State Automaton FSA.
- FSAs have an initial state and one or more acceptingstates, or goal states.
- State transition diagrams use a special arrow to indicate the inital state.
- A double circle is used to indicate the accepting state, or goal state.

Decision Tables
- A decision table is a precise yet compact way to model a complicated logic.
- Decision tables make it easy to observe that all possible conditions are accounted for.

Example
If X is greater than 6 and Y is less than 7 - then output "pass"
                                                              - else output "false"