Free A-Level Computer Science guide

Finite state machines, regular expressions and language syntax

AQA's regular-language content includes more than pattern matching. Connect sets of strings to states and transitions, then distinguish finite-state recognition from a recursively described syntax.

Content owner: Michael Print · Written for A-Level learners · Checked against official specifications

The idea to start with

A finite state machine remembers one of finitely many states and changes state for each input. An acceptor recognises a string by whether its final state is accepting; a Mealy machine produces output on its transitions. A transition table and a state diagram can express the same rules.

Regular expressions and finite state acceptors describe the same class of languages. BNF production rules can also express recursive syntax requiring unbounded matching, which a finite-state acceptor cannot represent in general.

AQA 7517 · 4.4.2.1–4.4.2.4, 4.4.3.1

Before you start

Useful foundations

Strings, Boolean conditions and loops
Basic diagrams and tables
The idea that a model has explicit rules

By the end, you should be able to

Interpret membership, set operations, Cartesian products and countability.
Draw or interpret simple state diagrams and equivalent transition tables.
Trace FSM acceptance and transition-based Mealy output.
Use the five specified regex operators and relate a regex to an FSM.
Check or write simple BNF rules and interpret an equivalent syntax diagram.

Sets and set operations

A set is unordered and has no duplicate members. With A = {a, b} and B = {b, c}, the statement a ∈ A is true. Cardinality is the number of members in a finite set.

A subset contains only members of the containing set. A proper subset also leaves out at least one member. A is a proper subset of {a, b, c}; A is a subset of itself, but not a proper subset.

A × B is the Cartesian product of ordered pairs: {(a, b), (a, c), (b, b), (b, c)}. Reversing the product changes what each pair position means.

Use the operation that matches the question

Union A ∪ B: {a, b, c}: keep members appearing in either set.
Intersection A ∩ B: {b}: keep members shared by both sets.
Difference A \ B: {a}: keep members of A that are absent from B.

Languages, empty strings and countability

A language is a set of strings. The empty set ∅ has no elements and cardinality zero. An empty language contains no strings; a language containing only the empty string has one member.

Set comprehension gives a membership rule. {n | n ∈ ℕ and n ≥ 2} means natural numbers at least 2, using ℕ = {0, 1, 2, …}. Its members can be listed against natural-number positions: it is countably infinite.

A finite set is also countable; an infinite set need not be, as the real numbers illustrate. Finite strings over a finite alphabet are countable: list increasing lengths, then alphabetical order within each length.

{0^n1^n | n ≥ 1} describes 01, 0011, 000111 and so on. The superscript means repetition: n zeros followed by n ones. This is an infinite set of finite strings.

A compact definition does not make this matching language regular. Remembering an unrestricted matching count requires more than finite-state tracking; a fixed finite number of states cannot retain every possible unmatched count.

Recognise strings ending in ab

Use alphabet {a, b}. S is the start and remembers no useful suffix; A remembers a suffix ending in a; F remembers a suffix ending in ab. F is the only accepting state.

Reading a from any state leads to A. Reading b from A leads to F; reading b from S or F leads to S. The complete transition table defines every state/input combination.

Draw S, A and F as nodes, an incoming start arrow to S and an accepting double circle around F. Draw each table entry as an arrow labelled with its input.

Check acceptance after consuming the whole input. Passing through F within baba does not accept the final string: its final a moves to A. The trace below instead accepts aab.

The equivalent regex (a|b)*ab permits any a/b prefix, including an empty prefix, followed by the required ab. Python fullmatch checks the whole string; finding a matching substring is a different task.

Trace aab: one transition for each symbol

Start at S
No input has been consumed. S is not accepting.
Read the first a
S → A: the current suffix ends in a.
Read the second a
A → A: the current suffix still ends in a.
Read b, then check
A → F: all input is consumed, and F is accepting.

Reaching F before input ends is insufficient: later symbols can change the state.

Complete transition table for strings ending in ab
State	Input a	Input b	Accepting?
S (start)	A	S	No
A	A	F	No
F	A	S	Yes

Use regex operators deliberately

Concatenation follows one pattern with another. a|b chooses an alternative; parentheses group a pattern; star repeats zero or more times; plus repeats one or more times; question mark makes one occurrence optional.

(ab)+c? accepts ab, abab and ababc, but rejects c and the empty string. (a|b)* includes the empty string, while (a|b)+ excludes it.

(ab)? permits either the whole pair or no pair; ab? requires a and makes only b optional. Build an FSM by tracking useful prefix information, rather than creating a state for every complete string.

Python re.sub(r"(ab)+", "X", "zzababyyab") returns zzXyyX, replacing each matching run of ab pairs. It finds regions inside the text; fullmatch instead asks whether the complete text belongs to the language.

Finite-state loops can accept infinitely many strings. Regular means representable by a regex or finite state acceptor, not finite or easy-looking. This guide uses only AQA’s named metacharacters; additional engine features do not define this formal-language scope.

Mealy output belongs to a transition

An invented exhibit gate has states Locked and Unlocked and inputs coin or push. The table specifies all four combinations: credit unlocks the gate, admit locks it, blocked leaves it locked and refund leaves it unlocked.

Label diagram edges input/output, such as coin/credit. Trace both new state and output at every step. AQA specifies Mealy machines for this output scope: output belongs to the transition.

Starting Locked, coin, coin, push, push produces credit, refund, admit, blocked and ends Locked. Repeated inputs can have different outputs because the current state is part of the rule.

Original Mealy gate rules
Current state	Input	Next state	Output
Locked	coin	Unlocked	credit
Locked	push	Locked	blocked
Unlocked	coin	Unlocked	refund
Unlocked	push	Locked	admit

Read BNF and syntax diagrams

BNF non-terminals name parts still to be expanded; terminals are the actual tokens. A production replaces a non-terminal with one allowed alternative. Here ε means the empty string.

For identifiers use <id> ::= <letter> <digits>, <letter> ::= a | b, <digits> ::= <digit> <digits> | ε, and <digit> ::= 0 | 1. These rules allow a or b followed by zero or more binary digits.

An equivalent syntax diagram requires a letter, then permits either immediate end or a repeatable digit path. Branches are alternative routes; loops are repetition. b101 follows a letter and three digit repetitions; 1b fails the first-letter rule.

Recursive syntax can describe matching counts

<pair> ::= 0 <pair> 1 | 01 describes the matching language. The derivation <pair> ⇒ 0 <pair> 1 ⇒ 0011 produces a valid string; repeated nesting generates any positive matching count.

A fixed finite state set cannot retain every possible unmatched count, but a recursive grammar can describe the structure. A syntax-diagram call back to its own non-terminal represents recursion, rather than an ordinary finite-state loop.

Worked example

Execute the acceptor and compare it with the regex

For aab, begin at S: input a gives A, the next a keeps A, and b gives F. The final state is accepting.
For baba, follow S → S → A → F → A. The final state is not accepting even though a prefix reached F.
Run the same six strings through the table implementation and re.fullmatch. Their two Boolean results agree. An input outside {a, b} raises ValueError in the FSM's explicit alphabet check.
For the gate, use its transition table rather than the acceptor rules. One transition returns both a new state and an output token; the output sequence follows the four inputs in order.

Exact acceptor output; final line is the Mealy output
Input	FSM result	Regex result
''	False	False
'ab'	True	True
'aab'	True	True
'baba'	False	False
'abab'	True	True
'abba'	False	False
Gate final output	Locked	['credit', 'refund', 'admit', 'blocked']

regular_languages.py — original Python 3 acceptor and Mealy tracePython

import re


def ends_ab(text):
    transitions = {"S": {"a": "A", "b": "S"},
                   "A": {"a": "A", "b": "F"},
                   "F": {"a": "A", "b": "S"}}
    state = "S"
    for symbol in text:
        if symbol not in {"a", "b"}:
            raise ValueError("outside the alphabet")
        state = transitions[state][symbol]
    return state == "F"


def gate(inputs):
    rules = {("Locked", "coin"): ("Unlocked", "credit"),
             ("Locked", "push"): ("Locked", "blocked"),
             ("Unlocked", "coin"): ("Unlocked", "refund"),
             ("Unlocked", "push"): ("Locked", "admit")}
    state = "Locked"
    outputs = []
    for token in inputs:
        if (state, token) not in rules:
            raise ValueError("outside the input alphabet")
        state, output = rules[(state, token)]
        outputs.append(output)
    return state, outputs


for text in ["", "ab", "aab", "baba", "abab", "abba"]:
    print(repr(text), ends_ab(text),
          re.fullmatch(r"(a|b)*ab", text) is not None)
print(gate(["coin", "coin", "push", "push"]))

Worked example

Construct a small recogniser from a rule

The rule is: one or more x symbols followed by an optional y. Its regex is x+y?.
Create start S, accepting X after at least one x, accepting Y after the optional y, and non-accepting dead state D. From S, x → X and y → D; from X, x → X and y → Y; from Y, either symbol → D; D loops on either symbol.
The empty string is rejected at S; xx is accepted at X; xxy is accepted at Y; xyy reaches D and is rejected. The dead state supplies explicit behaviour for strings that cannot become valid later.
Draw the same transitions as labelled arrows, marking the start arrow and accepting circles. The diagram and table must preserve all rules, including rejected inputs.

Original A-Level practice

7 original questions total 30 marks. Attempt each before opening the independently written indicative marking guidance.

Question 1

5 marks

For A = {1, 2} and B = {2, 3}, calculate A union B, A intersection B, A difference B and the cardinality of A × B. Explain whether A is a proper subset of A union B.

Show solution and marking guidance

Indicative answer

Union is {1, 2, 3} (1). Intersection is {2} (1). A difference B is {1} (1). The Cartesian product contains 2 × 2 = 4 ordered pairs (1). A is a proper subset because all its members occur in the union and 3 is an additional member (1).

Question 2

4 marks

Trace abbab through this FSM and decide whether it is accepted. Explain why reaching F before the final input would not by itself be sufficient.

FSM for this question

Begin in S and consume one input symbol per transition.

Transition rules
State	Input a	Input b	Accepting?
S (start)	A	S	No
A	A	F	No
F	A	S	Yes

Show solution and marking guidance

Indicative answer

The states are S → A → F → S → A → F (2). It is accepted because its final state is F (1). Acceptance concerns the complete input; later symbols can change an earlier accepting state (1).

Question 3

5 marks

For regex (ab)+c?, decide whether '', ab, ababc and abcabc are accepted and explain the optional part.

Show solution and marking guidance

Indicative answer

The empty string is rejected (1); ab is accepted (1); ababc is accepted (1); abcabc is rejected (1). The question mark permits at most one final c, while plus requires at least one complete ab repetition (1).

Question 4

4 marks

Starting Locked, trace push, coin, push, coin through this Mealy gate. Give the output sequence and final state, and state how outputs are labelled on its diagram.

Mealy gate for this question

State transitions and outputs
Current state	Input	Next state	Output
Locked	coin	Unlocked	credit
Locked	push	Locked	blocked
Unlocked	coin	Unlocked	refund
Unlocked	push	Locked	admit

Show solution and marking guidance

Indicative answer

Outputs are blocked, credit, admit, credit (2). Final state is Unlocked (1). An edge is labelled with input/output because output belongs to the transition (1).

Question 5

4 marks

Using these identifier BNF rules, explain why a01 is valid and 0a is invalid. Describe the required and repeatable paths of its syntax diagram.

Identifier grammar

The start symbol is <id>. Here ε denotes the empty string; | separates alternative productions.

BNF productions
Non-terminal	Production
<id>	<letter> <digits>
<letter>	a \| b
<digits>	<digit> <digits> \| ε
<digit>	0 \| 1

Show solution and marking guidance

Indicative answer

a01 has the required letter a followed by digits 0 and 1 (1). 0a fails the required first-letter rule (1). The diagram requires the letter path (1), then permits zero or more digit repetitions before end (1).

Question 6

4 marks

Use <pair> ::= 0 <pair> 1 | 01 to derive 000111. Explain why the full unbounded matching language needs more than a finite-state counter.

Show solution and marking guidance

Indicative answer

A derivation is <pair> ⇒ 0 <pair> 1 ⇒ 00 <pair> 11 ⇒ 000111 (2). Arbitrarily many zeros require arbitrarily many distinct unmatched counts to be distinguished (1), which a fixed finite set of states cannot retain (1).

Question 7

4 marks

Distinguish an empty language, a language containing only the empty string, and the set of all finite binary strings. Include cardinality or countability.

Show solution and marking guidance

Indicative answer

An empty language has no members and cardinality zero (1). The language containing only the empty string has cardinality one (1). All finite binary strings form an infinite set (1), but they are countable by listing increasing lengths and a fixed order within each length (1).

Specification and references

This guide addresses AQA 7517 4.4.2.1–4.4.2.4, 4.4.3.1. Check your examination year and the complete specification for the assessment scope.

These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.

Found an error? Email a correction.

Need help applying this to unfamiliar questions?

Use the free examples first, then explore one-to-one tuition if guided practice would help.

Explore tuition Email Michael

Free A-Level Computer Science guide

Finite state machines, regular expressions and language syntax

AQA's regular-language content includes more than pattern matching. Connect sets of strings to states and transitions, then distinguish finite-state recognition from a recursively described syntax.

Content owner: Michael Print · Written for A-Level learners · Checked against official specifications

The idea to start with

AQA 7517 · 4.4.2.1–4.4.2.4, 4.4.3.1

Before you start

Useful foundations

Strings, Boolean conditions and loops
Basic diagrams and tables
The idea that a model has explicit rules

By the end, you should be able to

Interpret membership, set operations, Cartesian products and countability.
Draw or interpret simple state diagrams and equivalent transition tables.
Trace FSM acceptance and transition-based Mealy output.
Use the five specified regex operators and relate a regex to an FSM.
Check or write simple BNF rules and interpret an equivalent syntax diagram.

Sets and set operations

A set is unordered and has no duplicate members. With A = {a, b} and B = {b, c}, the statement a ∈ A is true. Cardinality is the number of members in a finite set.

A subset contains only members of the containing set. A proper subset also leaves out at least one member. A is a proper subset of {a, b, c}; A is a subset of itself, but not a proper subset.

A × B is the Cartesian product of ordered pairs: {(a, b), (a, c), (b, b), (b, c)}. Reversing the product changes what each pair position means.

Use the operation that matches the question

Union A ∪ B: {a, b, c}: keep members appearing in either set.
Intersection A ∩ B: {b}: keep members shared by both sets.
Difference A \ B: {a}: keep members of A that are absent from B.

Languages, empty strings and countability

A language is a set of strings. The empty set ∅ has no elements and cardinality zero. An empty language contains no strings; a language containing only the empty string has one member.

{0^n1^n | n ≥ 1} describes 01, 0011, 000111 and so on. The superscript means repetition: n zeros followed by n ones. This is an infinite set of finite strings.

Recognise strings ending in ab

Use alphabet {a, b}. S is the start and remembers no useful suffix; A remembers a suffix ending in a; F remembers a suffix ending in ab. F is the only accepting state.

Reading a from any state leads to A. Reading b from A leads to F; reading b from S or F leads to S. The complete transition table defines every state/input combination.

Draw S, A and F as nodes, an incoming start arrow to S and an accepting double circle around F. Draw each table entry as an arrow labelled with its input.

Check acceptance after consuming the whole input. Passing through F within baba does not accept the final string: its final a moves to A. The trace below instead accepts aab.

Trace aab: one transition for each symbol

Start at S
No input has been consumed. S is not accepting.
Read the first a
S → A: the current suffix ends in a.
Read the second a
A → A: the current suffix still ends in a.
Read b, then check
A → F: all input is consumed, and F is accepting.

Reaching F before input ends is insufficient: later symbols can change the state.

Complete transition table for strings ending in ab
State	Input a	Input b	Accepting?
S (start)	A	S	No
A	A	F	No
F	A	S	Yes

Use regex operators deliberately

(ab)+c? accepts ab, abab and ababc, but rejects c and the empty string. (a|b)* includes the empty string, while (a|b)+ excludes it.

Mealy output belongs to a transition

Label diagram edges input/output, such as coin/credit. Trace both new state and output at every step. AQA specifies Mealy machines for this output scope: output belongs to the transition.

Starting Locked, coin, coin, push, push produces credit, refund, admit, blocked and ends Locked. Repeated inputs can have different outputs because the current state is part of the rule.

Original Mealy gate rules
Current state	Input	Next state	Output
Locked	coin	Unlocked	credit
Locked	push	Locked	blocked
Unlocked	coin	Unlocked	refund
Unlocked	push	Locked	admit

Read BNF and syntax diagrams

BNF non-terminals name parts still to be expanded; terminals are the actual tokens. A production replaces a non-terminal with one allowed alternative. Here ε means the empty string.

For identifiers use <id> ::= <letter> <digits>, <letter> ::= a | b, <digits> ::= <digit> <digits> | ε, and <digit> ::= 0 | 1. These rules allow a or b followed by zero or more binary digits.

Recursive syntax can describe matching counts

<pair> ::= 0 <pair> 1 | 01 describes the matching language. The derivation <pair> ⇒ 0 <pair> 1 ⇒ 0011 produces a valid string; repeated nesting generates any positive matching count.

Worked example

Execute the acceptor and compare it with the regex

For aab, begin at S: input a gives A, the next a keeps A, and b gives F. The final state is accepting.
For baba, follow S → S → A → F → A. The final state is not accepting even though a prefix reached F.
Run the same six strings through the table implementation and re.fullmatch. Their two Boolean results agree. An input outside {a, b} raises ValueError in the FSM's explicit alphabet check.
For the gate, use its transition table rather than the acceptor rules. One transition returns both a new state and an output token; the output sequence follows the four inputs in order.

Exact acceptor output; final line is the Mealy output
Input	FSM result	Regex result
''	False	False
'ab'	True	True
'aab'	True	True
'baba'	False	False
'abab'	True	True
'abba'	False	False
Gate final output	Locked	['credit', 'refund', 'admit', 'blocked']

regular_languages.py — original Python 3 acceptor and Mealy tracePython

import re


def ends_ab(text):
    transitions = {"S": {"a": "A", "b": "S"},
                   "A": {"a": "A", "b": "F"},
                   "F": {"a": "A", "b": "S"}}
    state = "S"
    for symbol in text:
        if symbol not in {"a", "b"}:
            raise ValueError("outside the alphabet")
        state = transitions[state][symbol]
    return state == "F"


def gate(inputs):
    rules = {("Locked", "coin"): ("Unlocked", "credit"),
             ("Locked", "push"): ("Locked", "blocked"),
             ("Unlocked", "coin"): ("Unlocked", "refund"),
             ("Unlocked", "push"): ("Locked", "admit")}
    state = "Locked"
    outputs = []
    for token in inputs:
        if (state, token) not in rules:
            raise ValueError("outside the input alphabet")
        state, output = rules[(state, token)]
        outputs.append(output)
    return state, outputs


for text in ["", "ab", "aab", "baba", "abab", "abba"]:
    print(repr(text), ends_ab(text),
          re.fullmatch(r"(a|b)*ab", text) is not None)
print(gate(["coin", "coin", "push", "push"]))

Worked example

Construct a small recogniser from a rule

The rule is: one or more x symbols followed by an optional y. Its regex is x+y?.
Create start S, accepting X after at least one x, accepting Y after the optional y, and non-accepting dead state D. From S, x → X and y → D; from X, x → X and y → Y; from Y, either symbol → D; D loops on either symbol.
The empty string is rejected at S; xx is accepted at X; xxy is accepted at Y; xyy reaches D and is rejected. The dead state supplies explicit behaviour for strings that cannot become valid later.
Draw the same transitions as labelled arrows, marking the start arrow and accepting circles. The diagram and table must preserve all rules, including rejected inputs.

Original A-Level practice

7 original questions total 30 marks. Attempt each before opening the independently written indicative marking guidance.

Question 1

5 marks

For A = {1, 2} and B = {2, 3}, calculate A union B, A intersection B, A difference B and the cardinality of A × B. Explain whether A is a proper subset of A union B.

Show solution and marking guidance

Indicative answer

Union is {1, 2, 3} (1). Intersection is {2} (1). A difference B is {1} (1). The Cartesian product contains 2 × 2 = 4 ordered pairs (1). A is a proper subset because all its members occur in the union and 3 is an additional member (1).

Question 2

4 marks

Trace abbab through this FSM and decide whether it is accepted. Explain why reaching F before the final input would not by itself be sufficient.

FSM for this question

Begin in S and consume one input symbol per transition.

Transition rules
State	Input a	Input b	Accepting?
S (start)	A	S	No
A	A	F	No
F	A	S	Yes

Show solution and marking guidance

Indicative answer

The states are S → A → F → S → A → F (2). It is accepted because its final state is F (1). Acceptance concerns the complete input; later symbols can change an earlier accepting state (1).

Question 3

5 marks

For regex (ab)+c?, decide whether '', ab, ababc and abcabc are accepted and explain the optional part.

Show solution and marking guidance

Indicative answer

The empty string is rejected (1); ab is accepted (1); ababc is accepted (1); abcabc is rejected (1). The question mark permits at most one final c, while plus requires at least one complete ab repetition (1).

Question 4

4 marks

Starting Locked, trace push, coin, push, coin through this Mealy gate. Give the output sequence and final state, and state how outputs are labelled on its diagram.

Mealy gate for this question

State transitions and outputs
Current state	Input	Next state	Output
Locked	coin	Unlocked	credit
Locked	push	Locked	blocked
Unlocked	coin	Unlocked	refund
Unlocked	push	Locked	admit

Show solution and marking guidance

Indicative answer

Outputs are blocked, credit, admit, credit (2). Final state is Unlocked (1). An edge is labelled with input/output because output belongs to the transition (1).

Question 5

4 marks

Using these identifier BNF rules, explain why a01 is valid and 0a is invalid. Describe the required and repeatable paths of its syntax diagram.

Identifier grammar

The start symbol is <id>. Here ε denotes the empty string; | separates alternative productions.

BNF productions
Non-terminal	Production
<id>	<letter> <digits>
<letter>	a \| b
<digits>	<digit> <digits> \| ε
<digit>	0 \| 1

Show solution and marking guidance

Indicative answer

a01 has the required letter a followed by digits 0 and 1 (1). 0a fails the required first-letter rule (1). The diagram requires the letter path (1), then permits zero or more digit repetitions before end (1).

Question 6

4 marks

Use <pair> ::= 0 <pair> 1 | 01 to derive 000111. Explain why the full unbounded matching language needs more than a finite-state counter.

Show solution and marking guidance

Indicative answer

A derivation is <pair> ⇒ 0 <pair> 1 ⇒ 00 <pair> 11 ⇒ 000111 (2). Arbitrarily many zeros require arbitrarily many distinct unmatched counts to be distinguished (1), which a fixed finite set of states cannot retain (1).

Question 7

4 marks

Distinguish an empty language, a language containing only the empty string, and the set of all finite binary strings. Include cardinality or countability.

Show solution and marking guidance

Indicative answer

An empty language has no members and cardinality zero (1). The language containing only the empty string has cardinality one (1). All finite binary strings form an infinite set (1), but they are countable by listing increasing lengths and a fixed order within each length (1).

Specification and references

This guide addresses AQA 7517 4.4.2.1–4.4.2.4, 4.4.3.1. Check your examination year and the complete specification for the assessment scope.

Found an error? Email a correction.

Need help applying this to unfamiliar questions?

Use the free examples first, then explore one-to-one tuition if guided practice would help.

Explore tuition Email Michael