ELEC5618 · Software Quality Engineering
Tools for Testing: FSMs and Markov Chains
Week 8 of University of Sydney ELEC5618 Software Quality Engineering models program behaviour for testing with finite state machines (states, inputs, transitions, outputs; Moore vs Mealy) and uses Markov chains for statistical, usage-based testing — including deriving transition probabilities from product logs. It surveys test-management tools. This is the quantitative touchpoint of the unit, and the probabilities render in plain notation with no display maths.
What this chapter covers
- 01Finite state machine elements: States (S), Inputs (I), Transitions (S × I → S), Outputs (O); the system is always in a current state and transitions are deterministic
- 02Moore machine (output depends on state only) vs Mealy machine (output depends on state and input)
- 03FSM representations: graphical (few states), state-transition table (many states), transition list (many states, few transitions)
- 04FSM vs control-flow graph: FSMs capture input-driven sequences and outputs; CFGs capture paths inside one function
- 05FSM fault types: state faults (missing/incorrect/extra) and transition faults (missing/incorrect/extra)
- 06Coverage: state coverage (each state reached) and transition coverage (each edge covered)
- 07Markov chains: transitions carry probabilities; outgoing probabilities from each state sum to 1; thresholding tests high-probability transitions
- 08Deriving transition probabilities from logs: count observed transitions per state, normalise by the state's total
Deriving Markov transition probabilities from usage logs
- +1Total the outgoing transitions from Browse: 12 + 4 + 4 = 20 observed transitions.
- +1Normalise each count by the total: P(Browse → Search) = 12/20 = 0.6; P(Browse → Cart) = 4/20 = 0.2; P(Browse → Exit) = 4/20 = 0.2.
- +1Verify the Markov constraint: the outgoing probabilities must sum to 1 — 0.6 + 0.2 + 0.2 = 1.0. Because this holds (and holds for every state), the annotated FSM is a valid Markov chain.
- +1Threshold-based prioritisation: with the probabilities ordered, Browse → Search (0.6) is the most-used path, so a usage-based strategy that tests only transitions above a probability threshold prioritises it — focusing effort on the part of the product users exercise most.
Key terms
- Finite state machine (FSM)
- A formalism modelling an object's dynamic behaviour over time as States, Inputs, Transitions (S × I → S) and Outputs. The system is always in a current state, and a given state-plus-input yields a single deterministic next state.
- Moore vs Mealy machine
- A Moore machine's output depends only on the current state (S → O); a Mealy machine's output depends on both the state and the input (S × I → O).
- FSM representations
- Graphical (nodes and arrows) for few states; a state-transition table (current state, input, next state, output) for many states; a transition list {S: (input, output, state), …} for many states with few transitions.
- FSM coverage
- State coverage requires each state to be reached by some test; transition coverage requires each edge to be exercised. The combined problem is finding the shortest set of paths that achieves both; uncovered transitions hint at missing test cases.
- Markov chain
- An FSM whose transitions carry probabilities, where P(i, j) is the probability of moving from state i to state j and the outgoing probabilities from every state sum to 1. Used for usage-based statistical testing.
- Transition probabilities from logs
- A way to estimate a Markov chain from data: parse the event log, count the transitions between states, and for each source state divide each transition count by the state's total so the row sums to 1.
Tools for Testing: FSMs and Markov Chains FAQ
What is the difference between a Moore and a Mealy machine?
Both are finite state machines; they differ in where the output comes from. A Moore machine's output depends only on the current state, so it changes when the state changes. A Mealy machine's output depends on both the current state and the input, so it can change on a transition even without changing state. Otherwise they share the same states, inputs and deterministic transitions.
When would I use an FSM instead of a control-flow graph?
Use an FSM when behaviour is driven by sequences of inputs and outputs matter — menu-driven or web applications, continuously operating systems — because an FSM captures the current state, input-dependent transitions and outputs. A control-flow graph lives inside a single function, treats transitions as pure sequence and ignores inputs and outputs, so it is for path analysis of code, not input-driven behaviour.
How do I turn usage logs into a Markov chain?
Parse the log, collect the states visited, and for each logged event record the transition to the next event's state, incrementing a count for that (from, to) pair. Then, for each source state, sum its outgoing transition counts and divide each count by that total to get a probability. If every state's outgoing probabilities sum to 1, you have a valid Markov chain you can test with a probability threshold.
Can AI help me with FSMs and Markov chains?
Yes. Sia can help you enumerate states and transitions, choose the right FSM representation, and normalise a count table into Markov transition probabilities while checking the sum-to-one constraint. Use it to rehearse the method; it does not do graded assessment, and the University of Sydney academic-integrity policy applies.
Exam move
This is the one week with numbers, so make the Markov procedure automatic: count outgoing transitions per state, divide by the state total, and confirm each row sums to 1 — that single constraint is the most common exam checkpoint. Be able to define an FSM formally (States, Inputs, Transitions, Outputs), distinguish Moore from Mealy in one line, and pick the right representation (graphical, table or transition list) for a given number of states and transitions. Keep the FSM fault taxonomy (missing/incorrect/extra states and transitions) and the two coverage criteria (state and transition) as short-answer lists. Know where transition probabilities come from — expert estimate, historical statistics, or instrumentation logs. Confirm the exam format on Canvas.
Working through Tools for Testing: FSMs and Markov Chains in ELEC5618? Sia is AskSia’s AI Software Engineering tutor — ask any ELEC5618 Tools for Testing: FSMs and Markov Chains question and get a clear, step-by-step explanation grounded in how ELEC5618 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
