Finite State Machine Simulator

What is a finite state machine?

A finite state machine is an abstract model of computation. It has a finite number of states, exactly one of which is active at any given moment, and it moves between those states in response to inputs according to a fixed set of transitions.

Every FSM has a start state, marked with an arrow coming from nowhere. A finite state automaton also has one or more accepting states, drawn as a double circle, which determine whether an input string is accepted or rejected.

How to trace a string through an FSM

This is the single most commonly examined skill on this topic, and the method never changes:

1. Start at the start state.
2. Read the first symbol of the input and follow the transition labelled with that symbol.
3. Repeat for every remaining symbol, in order, one transition per symbol.
4. When the input is exhausted, check where you finished.

The string is accepted only if you have consumed every symbol and ended in an accepting state. Both conditions must hold. If at any point there is no valid transition for the symbol you are reading, the string is rejected immediately.

Mistakes I see most often as an examiner

Marking this topic, the same handful of errors cost students marks year after year. They are all avoidable.

• Finishing in a non-accepting state and calling it accepted. Students trace correctly, run out of input, and then forget to check whether the final state is a double circle. Always do that final check explicitly.
• Stopping early. The whole string must be consumed. Reaching an accepting state part-way through means nothing if symbols remain.
• Forgetting to mark the start state. When asked to draw an FSM, an unmarked start state loses a mark even when the rest of the diagram is perfect.
• Missing transitions in a state transition table. Every combination of state and input symbol needs a row. Blank cells are treated as errors unless the question explicitly allows a partial machine.
• Confusing Mealy and Moore outputs. If outputs are written on the arrows it is a Mealy machine; inside the states it is a Moore machine. Putting them in the wrong place changes what the machine does.

State transition diagrams and tables

A state transition diagram and a state transition table hold identical information in different formats. The diagram draws states as circles and transitions as labelled arrows. The table lists every current-state-and-input pair with the resulting next state.

Exam questions ask you to convert between them in both directions, so practise both. Building a machine in the simulator above and then writing out its table by hand is a genuinely effective way to rehearse this.

Mealy and Moore machines

Not every FSM simply accepts or rejects — some produce output. In a Mealy machine the output depends on the current state and the current input, so outputs are labelled on the transitions. In a Moore machine the output depends only on the current state, so outputs are written inside the states. AQA A Level expects you to recognise and work with both.

Frequently asked questions