# 4.2 - Finite State Machines

- finite state machines = a way of representing a system using
- set of states
- transitions between states
- inputs and outputs
- = a machine of fixed possible states, set of allowable inputs (some of which can change the states) + set of outputs

- uses
- modelling the design of things (compilers, network protocols, hardware)
- FSMs’ states all yes/no (1/0).
- FSMs with output output 1/0
- No output = internal state updated only = AKA
**semiautomaton**

- accepting state = states which cause FSM to indicate 1
- FSMs with no outputs always have 1 or more accepting states

## Mathematical Definition

- deterministic finite automaton (DFA) = 5ple:
- \(ℚ\) = finite. non-empty set of states
- \(\sigma\) = finite, non-empty input ‘alphabet’ (set of symbols)
- \(\delta\) = series of transition functions
- \(q_0\) = initial state, an element of \(ℚ\)
- \(F\) = set of accepting states
- must be exactly 1 function for every input symbol in \(\sigma\) from each state

- non-determenistic finite automaton (NDFA or NFA)
- same 5ple as above, hower, unlike DFAs,
- not required to have transition functions for every symbol in \(\sigma\)
- multiple transition functions in same state for same symbol allowed
- new thing: null transitions = \(\epsilon\) = allow FSM to jump from one state to another without having to read a symbol

- Proven: DFAs can do everything NFAs can (and vice-versa). DFAs just might take more states+transitions

## Optimisation

- means finding machine with minimum no states that performs same function
- acyclic FSAs can be minimised \(O(n)\)

## FSM Diagrams

- circles = different states
- arrows = input value which correspond to the transitions between states
- two rings = accepting state

## Moore/Mealy Distinction

- in Mealy model, output is a function of present state + input, in Moore model, output is only function of only the present state