3.1.3 Finite State Machines

Finite State Machine (FSM)

• An FSM accepts inputs and processes an output
• Used extensively within computer science applications such as; Traffic light control systems, specifying a computer language, programs fro spell checking, networking protocols
• A state transition diagram is used to show the FSM as a picture

• Finite State Automato (FSA)
• This type of FSM has a finishing state and procedures only a yes/ no output based on the final state. E.g state 2 = Yes.      Other state = No

• FSMs with an output

1. MeaLy machine- Output on the transitions (arrows)
2. MoOre Machine- Output on the states (circles)

1. For example  0|A  The input is 0 while the output is A

  

    2. C is the output for state one, A for state 2 and B for state 3

A FSA which can be programmed easily

•  Transition table
• Shows the states and transitions in an FSM in table format

• Transition Function
• Transition functions show the states and transitions as a series of functions
• (Input Symbol, Current State) (Output Symbol, Next State)

• Deterministic and non- deterministic FSA
• A deterministic FSA has only one transition (arrow) for each input

• A non- deterministic FSA can have multiple transitions for an input. So there is more than one possible route around the state transition diagram

• FSM- Terminology Flash
• Halting state- is a state with no outputs

• Trigger- An input which triggers an output