Finite State Machines

A finite state machine (FSM) is a mathematical model of computation that can be in exactly one of a finite number of states at any given time. FSMs change state in response to inputs according to defined transition rules. They are covered in OCR H446 sections 1.4 and 2.1.

What Is a Finite State Machine?

Component	Definition
States	A finite set of conditions the machine can be in
Inputs	Symbols or events that cause the machine to change state
Transitions	Rules that define which state to move to for each input in each state
Start state	The state the machine begins in
Accept/final states	States that indicate the machine has completed successfully (in some FSMs)

Finite State Machines Without Output (FSAs)

A Finite State Automaton (FSA) or Finite State Acceptor processes an input string and either accepts or rejects it. There is no output other than accept/reject.

Example — FSA that accepts strings ending in "01":

Current State	Input 0	Input 1
S0 (start)	S1	S0
S1	S1	S2
S2 (accept)	S1	S0

Trace for input "1001":

Start in S0
Input 1: S0 -> S0
Input 0: S0 -> S1
Input 0: S1 -> S1
Input 1: S1 -> S2 (accept state)

Result: Accepted (the string ends in "01").

Trace for input "110":

Start in S0
Input 1: S0 -> S0
Input 1: S0 -> S0
Input 0: S0 -> S1

Result: Rejected (S1 is not an accept state).

State Transition Diagrams

State transition diagrams are the standard visual representation of FSMs:

Components:

Circles represent states
Arrows represent transitions, labelled with the input that triggers them
Double circles represent accept/final states
An arrow from nowhere points to the start state

    0        1
-->[S0] --------> [S0]
    |               ^
    | 0             | 1
    v               |
   [S1] --------> [[S2]]
    ^     1
    | 0
    +---+

(Where [[S2]] indicates a double circle = accept state)

Exam Tip: When drawing state transition diagrams, always clearly mark the start state (with an arrow from nowhere) and accept states (with double circles). Label every transition with its input.

State Transition Tables

A state transition table is the tabular equivalent of a state transition diagram:

Current State	Input	Next State
S0	0	S1
S0	1	S0
S1	0	S1
S1	1	S2
S2	0	S1
S2	1	S0

This is the same FSM as above, just in tabular form.

Advantages of each representation:

Representation	Advantage
Diagram	Easier to visualise the overall structure
Table	Easier to check that all transitions are defined; easier for complex FSMs