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