Finite state machines (FSMs)

Introduction to Finite State Machines (FSMs)

Welcome to one of the most logical and satisfying parts of Computer Science! Have you ever wondered how a vending machine knows you’ve put in enough money, or how a simple traffic light knows when to change? They use something called a Finite State Machine (FSM).

In this chapter, we will learn how to model systems that move from one "state" to another based on inputs. Don't worry if it sounds a bit technical at first—it’s essentially just a map showing how a system behaves! By the end of these notes, you'll be able to draw these maps and even use them to design simple computer logic.

What is a Finite State Machine?

At its heart, an FSM is a mathematical model of computation. It is a system that can be in exactly one of a finite number of states at any given time.

Analogy: The Light Switch
Think of a standard light switch. It has a "finite" number of states: it can either be ON or OFF. It cannot be both, and it cannot be half-way between. When you flip the switch (the input), the state changes. If it was OFF, it becomes ON. If it was ON, it becomes OFF.

Key Components of an FSM

To understand an FSM, you need to know these four things:
1. States: The different conditions the machine can be in (represented by circles).
2. Inputs: The events or triggers that cause change.
3. Transitions: The movement from one state to another (represented by arrows).
4. Outputs: What the machine produces (only in certain types of FSMs).

Quick Review: An FSM is like a "brain" for a simple machine. It remembers where it is (state) and waits for a nudge (input) to move somewhere else.

State Transition Diagrams

A State Transition Diagram is the visual way we draw an FSM. It looks like a collection of circles connected by arrows.

How to read the diagram:

• Circles: Each circle represents a State. The name of the state is usually written inside.
• The Start Arrow: An arrow pointing to a circle from "nowhere" marks the Initial State (the starting point).
• Arrows: These are Transitions. They show which way the machine moves when it receives an input. The input that triggers the move is written on the arrow.
• Double Circles: A circle with a double border is an Accepting State (or Stop State). This means the machine has successfully completed its task.

Example: A simple FSM to check if a binary string starts with '1'.
1. Start at State S0 (Initial State).
2. If the input is '1', follow the arrow to State S1 (Accepting State).
3. If the input is '0', follow the arrow to State S2 (Reject State).

Common Mistake: Forgetting to label the arrows! Without labels, we don't know which input causes which change.

State Transition Tables

Sometimes, a diagram can get messy if there are too many states. In those cases, we use a State Transition Table. This is just a grid that gives the exact same information as the diagram but in a text format.

How a table is structured:
• The left column lists the Current State.
• The top row lists the possible Inputs.
• The cells in the middle tell you the Next State.

Example Table:
Current State | Input: 0 | Input: 1
S0 | S0 | S1
S1 | S0 | S1

In this table, if you are in State S0 and receive a 1, you move to S1.

Key Takeaway: Diagrams are great for seeing the "flow," while tables are great for ensuring you haven't forgotten any possible inputs for each state!

FSMs with Output: Mealy Machines

The FSMs we've discussed so far just "accept" or "reject" a sequence. However, Oxford AQA students also need to know about Mealy Machines. These are FSMs that produce an output based on the current state and the input.

In a Mealy Machine diagram, the arrows are labeled as Input / Output.

Example: A Vending Machine
Imagine a machine where you need to reach 20 cents.
• State: 0 cents. Input: 10c. Transition: Move to "10 cents" state. Output: "Display 10".
• State: 10 cents. Input: 10c. Transition: Move to "Ready" state. Output: "Release Drink".

Mathematical Note: The output is determined by the transition. We write this as \( Input / Output \).

Did you know? Mealy machines are named after George H. Mealy, who was a pioneer in Bell Labs and helped develop these concepts for early telecommunications!

Summary and Tips for Success

Steps to build an FSM:

1. Identify the States: What are the distinct "situations" the system can be in?
2. Identify the Inputs: What can happen to change the situation?
3. Map the Transitions: For every state, decide what happens for every possible input.
4. Define Start/End: Clearly mark where the process begins and where it successfully finishes.

Memory Aid: The "S.I.T." Rule

To keep things simple, remember S.I.T.:
S - State (Where am I?)
I - Input (What just happened?)
T - Transition (Where do I go now?)

Final Quick Review:

• Finite: There is a limited number of states.
• Deterministic: In the FSMs you study, for any state and input, there is exactly one next state.
• State Transition Diagram: The visual map (circles and arrows).
• State Transition Table: The grid version of the map.
• Mealy Machine: An FSM that gives an output for every transition.

Don't worry if this seems tricky at first! Try drawing an FSM for something simple, like a microwave (States: Idle, Cooking, Paused). Once you can visualize the movement between states, the diagrams become second nature!