AQA A-Level Computer Science Paper 1, June 2025: Question 6

14 marks · Medium difficulty · Short Answer

Complete a state transition table for an FSM, analyse differences between alternative FSM diagrams, answer theoretical questions on regular expressions and sets, and write BNF production rules for arithmetic expressions.

Practise this question

Question

Question text

06 This question is about the CheckIfUserInputValid subroutine.

Figure 5 shows a finite state machine (FSM) represented as a state transition

diagram. The FSM is equivalent to the regular expression in the

CheckIfUserInputValid subroutine.

Figure 5

06.1 Complete the unshaded cells in Table 3 to represent the FSM in Figure 5 as a state

transition table.

Part of the first row has been completed for you.

Table 3

Initial state Input(s) New state

0–9

Copy the contents of the unshaded cells in Table 3 into the table in your

Electronic Answer Document. 13

[2 marks]

Figure 6 and Figure 7 show two attempts to represent the regular expression in the

CheckIfUserInputValid subroutine using a state transition diagram. There

are errors in both diagrams, as the FSM will either accept some strings that do not

match the regular expression or not accept some strings that do match the regular

expression.

Figure 6

Figure 7

06.2 Explain which strings accepted by the FSM in Figure 5 are not accepted by the FSM

in Figure 6.

[2 marks]

06.3 Explain which strings accepted by the FSM in Figure 7 are not accepted by the FSM

in Figure 5.

[2 marks]

06.4 Explain the purpose of the metacharacter $ in the regular expression in the

CheckValidNumber subroutine.

[1 mark]

06.5 Explain the difference between the metacharacters * and ? in regular expressions.

[1 mark]

06.6 A regular expression can be used to describe a set.

State two properties of sets that do not have to be true for a list.

[2 marks]

Infix expressions can normally use brackets.

The infix expressions entered by the user in the Skeleton Program cannot

use brackets.

06.7 Explain why a regular expression could not be used to check if an infix expression

entered by the user was valid if the infix expression was allowed to contain brackets.

[1 mark]

Figure 8 contains three rules for a language represented using Backus-Naur Form

(BNF).

Figure 8

<operator> ::= +|–|*|/

<digit> ::= 0|1|2|3|4|5|6|7|8|9

06.8 Add BNF rule(s) to the language shown in Figure 8 for an expression.

An expression should match all infix expressions currently accepted by the

Skeleton Program and also allow the infix expression to use brackets.

[3 marks]

Mark scheme

Show the mark scheme

Question Marks

06 1 All marks AO2 (analyse) 2

Initial state Input(s) New state

S0 0–9 S1

S1 0–9 S1

S1 + – * / S2

S2 0–9 S3

S3 0–9 S3

S3 + – * / S2

Mark as follows:

1 mark: any two correct rows

2 marks: all rows correct

I. order of rows

A. any reasonable format for input

06 2 All marks AO2 (analyse) 2

Strings in which any number/operand, other than the first,; contain an even number

of digits;

A. Other than the first number/operand; each number can only have an odd number

of digits;

06 3 All marks AO2 (analyse) 2

The empty string;

Strings consisting of just one number/operand;

Strings that start with an operator followed by an operand;

Max 2

06 4 Mark is for AO2 (analyse) 1

For June 2025 series item 6.4 has discounted. Examiners must award all students 1

mark for item 6.4

06 5 Mark is for AO1 (understanding) 1

(Both mean the preceeding character/element is optional, but) ? allows at most one

of the character/element whereas * allows an unlimited–A-LEVEL COMPUTER SCIENCE/anyof the – –

character/element;

14 06 6 All marks for AO1 (understanding) 2

Unordered;

No duplicate values;

06 7 Mark is for AO2 (apply) 1

Can’t ensure that there are equal number of open and close brackets // can’t ensure

that the count/number of two different items is the same (when there can be any

number of those items);

Can’t do both left- and right-recursion (only one of the two);

A. FSMs do not have a memory

Max 1

06 8 All marks AO2 (apply) 3

<expression> ::= <number><operator><number> |

(<expression>)|<expression><operator><number>|<number><o

perator><expression>

Alternative answer

<expression> ::= (<expression>)

Mark as follows:

• 1 mark: one of the four definitions for expression is correct

• 2 marks: two of the four definitions for expression is correct

• 3 marks: fully correct answer

DPT. Minor errors in notation used

How to answer it

Finite State Machines, Regular Expressions & Backus-Naur Form

What this question tests

This question evaluates your theoretical and practical grasp of formal languages and automata theory from Section 4.4 of the AQA specification:

FSM Transition Tables: Mapping visual states, inputs, and transitions into tabular form accurately.
Automata Tracing & Logic: Identifying non-accepted vs accepted string structures created by subtle diagram logic errors (e.g. parity/loop traps).
Regular Expression Syntax: Understanding quantifier metacharacters ( * vs ? ) and position anchors ( $ ).
Data Structures: Contrasting mathematical sets with programmatic lists.
Language Classes & BNF: Knowing the computational limits of Regular Languages (inability to handle arbitrary nested structures) and writing recursive context-free grammars in Backus-Naur Form.

Question 06.1 • 2 Marks

State Transition Table for Figure 5

Translating State Transition Diagrams to Tables

Figure 5 models an infix expression validating loop where:

S0: Start state, transitions on initial digit to S1.
S1: Loop on digits, transitions on an operator + | - | * | / to S2.
S2: Requires another digit to transition to S3.
S3: Double-ringed (accepting state); can loop on digits, or transition on an operator back to S2.

✅ Completed Table 3

Initial state	Input(s)	New state
S0	0–9	S1
S1	0–9	S1
S1	+ - * /	S2
S2	0–9	S3
S3	0–9	S3
S3	+ - * /	S2

🧠 Exam Technique & Marking

Marking Allocation:

1 mark: Any 2 correct transition rows.
2 marks: All 6 rows completely correct.

Tip: The order of rows does not matter. Input symbols can be formatted as individual rows or listed as + | - | * | / or + - * / .

Question 06.2 • 2 Marks

Flaw Analysis in Figure 6: The Alternating Digit Loop

Explaining strings accepted by Figure 5 but rejected by Figure 6

📐 Step-by-Step Diagram Tracing

In Figure 6, after an operator transition from S4 to S5, we read the second operand.
Inputting 1 digit moves from S5 to S6 (Accepting).
Inputting a 2nd digit moves from S6 back to S5 (Non-accepting).
Inputting a 3rd digit moves back to S6 (Accepting).
Conclusion: S6 is only reached on odd numbers of digits for any operand after the first operator!

✅ Mark Scheme Answer

Strings where any operand/number other than the first contains an even number of digits [2 marks].
Alternative wording accepted: Except for the first operand, numbers are restricted to having only an odd number of digits [2 marks].

❌ Common Misconceptions

Students often vaguely state: "It doesn't accept multi-digit numbers". This earns 0 marks because it does accept multi-digit numbers of odd length (e.g., 3 digits like 123 or 5 digits like 45678). You must specifically identify that numbers with an even number of digits are rejected.

Question 06.3 • 2 Marks

Flaw Analysis in Figure 7: Over-Permissive FSM

Strings accepted by Figure 7 that are NOT accepted by Figure 5

✅ Any Two of the Following (1 mark each, Max 2):

The empty string ( ε ): S7 is both the start state and an accepting state with no inputs consumed.
Strings consisting of only a single number/operand: e.g., "42" (Figure 5 requires at least one operator and second operand to reach S3).
Strings that start with an operator: (e.g., "+5" or "* 2" ), because S7 has an immediate transition on an operator to S9.

🧠 Visual Clues to Look For

Notice the start arrow enters S7, and S7 has a double circle. Whenever an initial state is double-circled, the empty string is always accepted!
Check outgoing transitions from the start state: S7 accepts operators immediately, which Figure 5 never allows.

Questions 06.4 & 06.5 • 1 Mark Each

Regular Expression Metacharacters

💡 06.4: The Purpose of $

Answer: Asserts/matches the end of the string (or line).

It ensures that no extra trailing invalid characters can follow the matched pattern.

Note: In the June 2025 examination series, item 6.4 was discounted and all students received 1 mark automatically. However, knowing the anchor function of ^ (start) and $ (end) is core syllabus knowledge!

💡 06.5: Difference between * and ?

Answer: Both make the preceding item optional (0 occurrences), but:

? matches zero or one occurrence (at most one).
* (Kleene star) matches zero or more occurrences (an unlimited number).

Award 1 mark for stating that both indicate optionality/zero occurrences, but ? allows at most one while * allows unlimited.

Question 06.6 • 2 Marks

Mathematical Sets vs Lists

Data Structure Theory (AO1)

✅ Properties of Sets (1 mark each):

Unordered: Sets have no defined sequence or index order; elements do not occupy specific positional slots.
No duplicate values: All elements in a set must be unique (each member can appear only once).

❌ Pitfalls to Avoid

Do not say "sets can only store numbers" — sets are type-agnostic.
Do not say "lists are static and sets are dynamic" — this confuses abstract mathematical definitions with concrete language implementations.

Question 06.7 • 1 Mark

Theoretical Limits of Regular Languages

Why can't regular expressions parse nested brackets?

💡 The Chomsky Hierarchy & Memory

Regular expressions correspond to Type 3 languages (Finite State Automata). An FSM has a strictly finite set of states and no storage memory or stack.

Arbitrarily nested brackets require counting an unknown number of open brackets and matching them to corresponding closing brackets in reverse order (LIFO), which requires a Pushdown Automaton (Context-Free Language / Type 2).

✅ Mark Scheme Accepted Answers (Max 1)

Cannot ensure that there are an equal number of opening and closing brackets // cannot ensure counts match for an arbitrary number of items.
FSMs / Regular expressions do not have memory.
Cannot perform both left- and right-recursion simultaneously.

Question 06.8 • 3 Marks

Writing BNF Rules for Infix Expressions with Brackets

Context-Free Grammars in Backus-Naur Form

Given existing rules in Figure 8:

✅ Correct BNF Rule(s) for <expression>

Single-line format:

Equivalent multi-line format:

🧠 Mark Breakdown & Logic

1 mark: Any 1 of the 4 definition clauses correct.
2 marks: Any 2 of the 4 definition clauses correct.
3 marks: Fully correct definition covering base infix, bracketed nesting, and recursive chaining.

Rule anatomy:

<number><operator><number> handles base arithmetic (e.g. 3+4).
(<expression>) introduces brackets around any valid expression.
<expression><operator><number> and vice-versa allow chaining (e.g. 3+4*5 or (2+3)*4).

Topics

4.4 Theory of computation · 4.4.2 Regular languages · 4.4.3 Context-free languages

Question and mark scheme from the AQA A-Level Computer Science examination, Paper 1, June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.