Mastering Finite State Machines for A-Level Computer Science

In the study of computation, a Finite State Machine (FSM) is a powerful mathematical model used to represent the behaviour of systems that exist in a finite number of conditions. Whether you are designing a vending machine, a traffic light controller, or a lexical analyser for a compiler, FSMs provide the formal logic required to transition between states based on specific inputs.

For your A-Level Computer Science exams, understanding FSMs is essential. You will be expected to interpret state transition diagrams, construct state transition tables, and identify whether a machine is deterministic. This article breaks down these concepts into manageable parts, ensuring you have the tools to tackle any FSM problem with confidence.

What is a Finite State Machine?

An FSM is an abstract machine that can be in exactly one of a finite number of states at any given time. It changes from one state to another in response to external inputs; this change is called a transition.

Every FSM consists of:

• States: The distinct conditions the machine can be in (e.g., 'Locked', 'Unlocked').
• Inputs: The events or data that trigger a change.
• Transitions: The rules defining how the machine moves from one state to another based on the current state and input.
• Start State: The initial condition of the machine.
• Accepting (or Final) States: Specific states that indicate the input sequence has been successfully processed.

Visualising with State Diagrams

State diagrams are the visual representation of an FSM. States are drawn as circles, and transitions are represented by arrows connecting these circles. The arrow is labelled with the input that triggers the transition.

Worked Example 1: A Simple Turnstile

Imagine a turnstile that starts in a 'Locked' state. If you insert a coin, it moves to an 'Unlocked' state. If you push the gate while 'Unlocked', it returns to 'Locked'.

1. States: {Locked, Unlocked}
2. Start State: Locked
3. Transitions:
   • (Locked, Coin) $\to$ Unlocked
   • (Unlocked, Push) $\to$ Locked

In a diagram, you would draw two circles. An arrow from outside points to 'Locked'. An arrow labelled 'Coin' goes from 'Locked' to 'Unlocked', and an arrow labelled 'Push' goes from 'Unlocked' to 'Locked'.

State Transition Tables

While diagrams are great for visualisation, state transition tables are better for formal analysis. They list every possible current state and the resulting next state for every possible input.

Worked Example 2: Binary Parity Checker

Consider an FSM that checks if a binary string has an even number of 1s.

• States: S0 (Even number of 1s), S1 (Odd number of 1s).
• Start State: S0 (0 is an even number).
• Accepting State: S0.

| Current State | Input 0 | Input 1 | | :--- | :--- | :--- | | S0 | S0 | S1 | | S1 | S1 | S0 |

If the input is '1', the machine moves from S0 to S1. If another '1' arrives, it moves from S1 back to S0. This table clearly defines the logic for any input sequence.

Deterministic Finite State Machines (DFSM)

A Deterministic Finite State Machine (DFSM) is a specific type of FSM where, for every state and every input, there is exactly one transition to a next state. There is no ambiguity. If you are in state A and receive input '1', you know exactly where you will end up. Most A-Level questions focus on deterministic models because they are predictable and easier to implement in hardware or software.

Common Mistakes to Avoid

1. Forgetting the Start State: Always ensure your diagram has an arrow pointing to the start state from 'nowhere'. Without it, the machine has no defined beginning.
2. Missing Transitions: In a deterministic FSM, every state must have a defined transition for every possible input. If your machine receives an input and has no arrow for it, the machine 'crashes' or is incomplete.
3. Confusing States with Outputs: Remember that states represent the 'memory' of the machine. Do not label states with the output unless you are specifically drawing a Moore machine where the output is tied to the state.

Frequently Asked Questions

What is the difference between a state and an input? A state is a condition the machine is currently in (e.g., 'Waiting'), while an input is the external signal that causes the machine to change its state (e.g., 'Button Pressed').

Can an FSM have multiple accepting states? Yes. An FSM can have one or more accepting states. If the machine finishes in any of these states after processing the input, the input is considered 'accepted'.

What happens if an input is not defined for a state? In a strictly deterministic FSM, this is an error. In practice, it often means the machine will reject the input or remain in the current state, depending on the system design.

Conclusion

Finite State Machines are a fundamental concept that bridges the gap between abstract logic and physical hardware. By mastering state diagrams and transition tables, you are building the foundation for understanding how computers process complex instructions. To see these concepts in action, head over to MathInstructor AI to generate a free, narrated animated lesson on Finite State Machines and watch the logic unfold before your eyes.