3.1.3 - Finite State Machines

• An FSM accepts input and processes an output.

Examples of where they are used would be things such as:
- Traffic Light Control System
- Programs for spell checking
- Networking Protocols

• A State Transition Diagram

These are used to show the FSM as a picture where the plain arrow is the starting state#

• Finite State Automata (FSA)

This type of FSM has a finishing state and produces only a YES or No , depending on the final state. for exmple S2 in the diagram below would give Yes any other state would give No.

• There are Two types of FSM:

- Mealy Machines

   - This gives an output on the Transitions (Arrows)

- Moore Machines

   - This gives an output on the states (Cricles)

• FSM Transition Table

A Transition Table shows the states and Tranistion in a FSM in table format, as shown above.

• Transition Functions

These show the sates and tranistions as a serious or written functions:

(Input Symbol, Current State)  -> (Output Symbol, Next State)

this can be taken and used to generate a program to show the operation of the FSA

• Deterministic and Non - Deterministic FSA

A Deterministic FSA has one and only one transition (arrow) for each input.

A Non- Deterministic FSA can have multiple transitions for and input. Meaning there is more than  one possible route around the State Transition Diagram

Halting States - These are states with no outputs

• Summary:

1. Finite State Machines (Input, Process, Output)
2. Sate Transition Diagram (Shows FSM as picture)
3. Finite State Automata (Gives only Yes on a finishing state or a No as an output)
4. Mealy Machine (Output on Transitions)
5. Moore Machine ( Output on State)
6. Transition Table ( Table showing States and Transitions in an FSM)
7. Transition Function (Shows transitions in a series of functions)
8. Deterministic and Non- Determisnitc FSA (Output with one and Output with more than on)
9. Halting State (No Outputs)

3.1.2 - Comparing Algorithms

Problems with different time complexities

Constant Complexity O(1) - This algorithm takes the same amount of time no matter how big the problem is.

Linear Complexity O(n) - As the size of the problem increases, the time taken to solve the problem grows at the same rate. (Proportional) Less efficient

Logarithmic Complexity O(log n) - As the size of the problem grows, the time take to solve the problem increases, but at a slower rate.

Polynomial Complexity O(nk) - As the size of the problem grows, the time taken to solve it grows faster, but can be solved in a reasonable amount of time.

Expotential Complexity O(kn) - As the size of the problem grows, the time taken to solve it grows by larger and larger amounts, Only small size version of these problems can be solved in a reasonable amount of time

Factorial Complexity O(n!) - Even worse than exponential. cannot be solved in a reasonable amount of time.

3.1.1 - Information Hiding & Abstraction

Information Hiding - Hiding the design complexity of a  system to simplify it for the user

• e.g. Windows - unaware of the underlying complexity behind the system

Abstraction - This is where any unnecessary details are removed from the system (Information Hiding)

• e.g. Tube maps - no relation to real life distances at all

Generalisation -  In computing this would be wear only the main principles of a computer system is shown and not the rest of the program, for example a top down design.

Representation - Simplifying a complex system such as phone masts that do not have numbers, distances etc.

Levels of abstraction:

1. Application (Word processing) - High levels of abstraction.
2. High level programming languages (VB) - hides low level commands such as what the IF statement does.
3. Machine Code - Hides the complexity of the underlying electronics behind a machine code commands.
4. Electronics - Hides the physical process of atoms & neutrons with basic electronics components.