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)