AQA A-Level Computer Science (7517)

## Learning Outcomes

- Understand what a finite state machine is and why it is used in computation
- Identify states, inputs, transitions, start states, accepting states and outputs on FSM diagrams and tables
- Convert between a state transition diagram and a state transition table
- Trace an input string through an FSM to decide whether it is accepted
- Explain the difference between FSMs with output and FSMs without output
- Distinguish carefully between deterministic and non-deterministic finite state machines
- Apply FSMs to both real-world systems and language recognition problems

## AQA A-Level Computer Science (7517) Syllabus

For the AQA A-Level Computer Science (7517), you are expected to understand finite state machines with and without output, with a focus on the following syllabus points:

- Know that an FSM has a finite number of states and can only be in one state at a time
- Identify the role of inputs, transitions, start states and accepting states
- Interpret and create state transition diagrams from a problem statement
- Interpret and create state transition tables from a problem statement or diagram
- Understand how an FSM without output can accept or reject strings
- Determine whether a given string is valid by tracing it from the start state to a final state
- Understand that some FSMs produce outputs during transitions or operation
- Explain the difference between deterministic and non-deterministic FSMs in safe exam terms

## Test Your Knowledge

_Attempt these questions before reading this article. If you find some difficult or cannot remember the answers, look more closely at that area during your revision._

1. What is a finite state machine, and why is it described as finite?
2. How can you tell the difference between a start state and an accepting state on a state transition diagram?
3. How do you decide whether a string is accepted by an FSM with no output?
4. What is the difference between a state transition diagram and a state transition table?
5. How does an FSM with output differ from one that only recognises valid strings?

## Introduction

Finite state machines are one of the clearest examples of an abstract model in Computer Science. They are not usually physical machines. Instead, they are a way of describing how a system behaves when it receives inputs over time. The key idea is simple: the system is always in one current state, and each new input may make it move to another state.

In AQA A-Level Computer Science, FSMs matter for two reasons. First, they are used to model real systems such as login systems, vending machines and control circuits. Second, they are used as recognisers: they can test whether a string belongs to a language by checking where the machine ends after reading the whole string.

> **Key Term: finite state machine (FSM)**
> A computational model with a finite number of states, where the current state changes according to inputs and transition rules, and may also produce outputs.

### Core structure and terminology of finite state machines

To answer exam questions well, you need more than a vague definition. You need to know exactly what each part of an FSM does and why it is there.

A finite state machine has a limited set of possible states. This means it does not need unlimited memory. Instead, it stores only enough information to know what situation it is currently in. For example, a login system may only need to know whether no username has been accepted yet, whether the username has been accepted but the password has not, or whether access has been granted.

This gives three possible states:

- S0: waiting for a correct username
- S1: correct username entered, waiting for password
- S2: access granted

The machine can only be in one of these states at any moment. That point is easy to forget in long questions. An FSM does not partly occupy two states at once unless the question is about non-determinism, which should be handled very carefully.

> **Key Term: state**
> A condition or status that the machine can be in at a particular moment.

A change from one state to another is called a transition. Transitions happen because of an input or condition. In a diagram, states are shown as circles and transitions as directed arrows.

> **Key Term: transition**
> A change from one state to another caused by an input or condition.

A state transition diagram usually includes a start state. This is shown by an arrow pointing into the state from nowhere. If the FSM is being used to recognise strings, it may also have one or more accepting states, shown as double circles.

> **Key Term: start state**
> The state where the machine begins before any input has been processed.
>
> **Key Term: accepting state**
> A state which means the input is accepted if the machine finishes there after all input has been read.

Students often mix up start and accepting states. They are not the same thing. A start state is where processing begins. An accepting state is where processing must end for a string to be valid. Sometimes one state can be both, but you should not assume that unless the diagram shows it.

A good example is the light switch model. The states are simply Light Off and Light On. There is one input, button pressed or not pressed. The important design idea is that every relevant input must be accounted for in every state. If the light is off and the button is not pressed, it stays off. That is still a valid transition, even though nothing seems to happen. In FSM terms, "no change" is still a defined next state.

This is why good FSMs force precise thinking. They make you ask: what happens for each possible input in each state?

> **Test Tip:** When drawing an FSM from a scenario, list the states first, then list every possible input, and only then add transitions. This reduces missing arrows, which is a common exam error.

### State transition diagrams and state transition tables

AQA questions often move between diagram and table forms. You need to be fluent in both.

A **state transition diagram** is visual. It helps you see the overall structure quickly:

- circles represent states
- an incoming arrow marks the start state
- double circles mark accepting states
- labelled arrows show transitions
- labels may show input only, or input and output

A **state transition table** shows the same information in tabular form. It usually lists the current state, the input, and the next state. If the FSM has output, the output is included too.

> **Key Term: state transition diagram**
> A graphical representation of an FSM using states as circles and transitions as labelled arrows.
>
> **Key Term: state transition table**
> A table showing how each current-state and input combination leads to a next state, and sometimes an output.

Consider this login example:

- From S0, incorrect username keeps the machine in S0 and gives an error
- From S0, correct username moves to S1
- From S1, incorrect password keeps the machine in S1 and gives an error
- From S1, correct password moves to S2

This can be written as a table:

| Input              | Current state | Next state | Output        |
| ------------------ | ------------- | ---------- | ------------- |
| Incorrect username | S0            | S0         | Error message |
| Correct username   | S0            | S1         | null          |
| Incorrect password | S1            | S1         | Error message |
| Correct password   | S1            | S2         | null          |

The table is useful because it shows every defined rule clearly. In design work, tables often make omissions easier to spot. Diagrams are easier for following paths visually. Neither is "better" in all situations. They are two representations of the same logic.

A common exam task is converting one form into the other. To convert a diagram into a table:

1. Write down all states.
2. Identify every input shown.
3. For each state-input pair, record the next state.
4. Add output if the machine has one.

To convert a table into a diagram:

1. Draw each state once.
2. Mark the start state.
3. Mark accepting states if relevant.
4. Draw an arrow for each row using the correct label.

Students often lose marks by missing self-loops. If an input keeps the machine in the same state, you still need an arrow from the state back to itself.

> **Test Tip:** In a table-completion question, check whether every state has a defined outcome for every allowed input. Missing one combination is a standard source of dropped marks.

### FSMs without output: recognising valid strings

FSMs without output are often used as recognisers. Their job is not to generate messages or actions. Their job is to answer a yes/no question: is this string in the language?

A string is processed one symbol at a time, from left to right. You always begin at the start state. After the final symbol has been read, acceptance depends only on the finishing state.

> **Key Term: valid string**
> An input string that is accepted by the machine because, after all symbols are processed, it ends in an accepting state.

Suppose an FSM defines valid identifiers with these rules:

- the first character must be a lowercase letter
- any following characters may be lowercase letters or digits
- length may be one or more

One possible design is:

- S1: start state, before any character is read
- S2: accepting state, valid identifier so far
- S3: dead state, invalid string

How it works:

- from S1, a lowercase letter leads to S2
- from S1, a digit leads to S3
- from S2, a lowercase letter or digit stays in S2
- from S3, any allowed input stays in S3

Now trace some strings.

String: `a`

- Start at S1
- Read `a` -> move to S2
- Input finished, and S2 is accepting
- So `a` is accepted

String: `b7a`

- Start at S1
- Read `b` -> S2
- Read `7` -> S2
- Read `a` -> S2
- Finish in S2
- Accepted

String: `4ab`

- Start at S1
- Read `4` -> S3
- Read `a` -> S3
- Read `b` -> S3
- Finish in S3
- Rejected

This shows an important idea: acceptance is decided after the whole string is consumed, not halfway through. A string can pass through an accepting state and still later be rejected if later input moves it elsewhere.

Some FSMs include a dead state, also called a trap state. Once the machine enters it, no remaining input can ever lead to acceptance. This is useful in recognisers because invalid input can be handled cleanly.

Another classic example is a language that accepts strings of the form `ababab...` including the empty string. A compact machine can use:

- S0 as the start and accepting state
- S1 as "just seen a"
- D as dead state

Transitions:

- from S0, `a` -> S1, `b` -> D
- from S1, `b` -> S0, `a` -> D
- from D, both `a` and `b` -> D

This accepts:

- empty string
- `ab`
- `abab`
- `ababab`

It rejects:

- `a`
- `aba`
- `abb`
- `ba`

Why? Because only complete `ab` pairs return the machine to accepting state S0.

This is the kind of logic examiners want to see: not just the answer, but the path.

### FSMs with output, determinism and common exam traps

Some FSMs do more than accept or reject strings. They also produce outputs while running. In these machines, the output is part of the system behaviour, not just the final judgement.

In the login example, the system may output an error message when the username or password is incorrect. That means the machine is not just a recogniser. It is modelling behaviour.

> **Key Term: output**
> A value, signal or action produced by an FSM as it processes an input or changes state.

At AQA level, the secure distinction is this:

- **FSM without output**: usually used to recognise whether a string is accepted
- **FSM with output**: changes state and also produces outputs during operation

You may also meet the term **Mealy machine**.

> **Key Term: Mealy machine**
> A type of FSM with output where the output is associated with transitions and depends on the current state and input.

You do not need to turn every FSM-with-output question into a full theory answer about Mealy and Moore machines unless the question asks for it. What matters most is reading the diagram or table correctly and recording outputs in the correct order.

Worked example: trace a login sequence.

Machine rules:

| Input              | Current state | Next state | Output |
| ------------------ | ------------- | ---------- | ------ |
| Incorrect username | S0            | S0         | Error  |
| Correct username   | S0            | S1         | null   |
| Incorrect password | S1            | S1         | Error  |
| Correct password   | S1            | S2         | null   |

Input sequence:

1. Incorrect username
2. Correct username
3. Incorrect password
4. Correct password

Step-by-step trace:

1. Start in S0  
   Incorrect username -> stay in S0, output `Error`

2. Current state S0  
   Correct username -> move to S1, output `null`

3. Current state S1  
   Incorrect password -> stay in S1, output `Error`

4. Current state S1  
   Correct password -> move to S2, output `null`

Final state: S2  
Outputs produced in order: `Error, null, Error, null`

Students often make three mistakes here:

- they update the state incorrectly after each input
- they forget to record outputs at each step
- they assume only the final state matters, when the question may also ask for outputs along the path

A further distinction you should know is deterministic versus non-deterministic.

> **Key Term: deterministic finite state machine**
> An FSM in which each state and input pair leads to exactly one next state.
>
> **Key Term: non-deterministic finite state machine**
> An FSM in which a state and input pair may allow more than one possible next state.

In deterministic machines, once you know the current state and the next input, the next state is fixed. This makes tracing straightforward.

In non-deterministic machines, one input may lead to several possible paths. A string is accepted if at least one path ends in an accepting state. For AQA, treat this as a distinction in terminology rather than the main focus unless the question directly targets it.

Side-by-side comparison:

| Feature                           | Deterministic FSM                | Non-deterministic FSM                  |
| --------------------------------- | -------------------------------- | -------------------------------------- |
| Next state for a state/input pair | Exactly one                      | One, many, or none                     |
| Tracing a string                  | Single path                      | Multiple possible paths                |
| Acceptance rule                   | End in accept state on that path | At least one path ends in accept state |

The safest exam wording is simple: deterministic means one possible next state for each state-input pair.

## Key Point Checklist

_This article has covered the following key knowledge points:_

- A finite state machine is a model with a finite number of states and transition rules
- An FSM can only be in one state at a time
- States are shown as circles and transitions as directed arrows on a state transition diagram
- The start state is shown by an incoming arrow and an accepting state is shown by a double circle
- A state transition table shows current state, input, next state and sometimes output
- An FSM without output is often used to recognise whether a string is valid
- A string is accepted only if the machine finishes in an accepting state after all input has been read
- Self-loops matter and must be included when an input leaves the machine in the same state
- FSMs with output model systems that generate actions or signals as they process input
- A Mealy machine is an FSM where output is associated with transitions
- A deterministic FSM has exactly one next state for each state-input pair
- A non-deterministic FSM may allow more than one possible next state for a given state-input pair

## Key Terms and Concepts

- finite state machine (FSM)
- state
- transition
- start state
- accepting state
- state transition diagram
- state transition table
- valid string
- output
- Mealy machine
- deterministic finite state machine
- non-deterministic finite state machine


Theory of Computation - Finite state machines