Theory of computation (FSMs, regular expressions, BNF, Turing machines, Big-O) – A-level Computer Science exam questions with mark scheme

1Core4 marks

The finite state machine (FSM) below has start state A and accepting state C. The input alphabet is {0, 1}.

(a) State whether the input 10101 is accepted. Justify your answer. [1]

(b) State whether the input 0110 is accepted. Justify your answer. [1]

(d) Write a regular expression that defines the same language as this FSM. [1]

(a) Accepted – path A, A, B, C, B, C ends in the accepting state C (both the decision and the final state/path needed)(1)
(b) Not accepted – path A, B, C, A, B ends in state B, which is not an accepting state (both the decision and the final state/path needed)(1)
(c) All strings (of 0s and 1s) that end in 01; NE 'strings containing 01'(1)
(d) (0|1)*01; accept any equivalent expression that matches exactly the strings ending in 01, e.g. (1|0)*01(1)
Answer: (a) Accepted (ends in C) (b) Rejected (ends in B) (c) Strings ending in 01 (d) (0|1)*01
Examiner tip: Always finish the trace and check whether the LAST state is accepting; passing through C earlier does not count.

2Standard4 marks

A regular expression is a(b|c)*d.

(a) The strings below are tested against the whole regular expression. Identify which strings match.

ad abcd abbcb acbbd abdd aabd [2]

(b) Write a regular expression for the set of all strings of 0s and 1s that start with 1 and end with 0. [2]

(a) Correctly identifies matches: ad, abcd, acbbd (at least two of the three correct with no incorrect strings)(1)
(a) All three matching strings and no others(1)
(b) 1 at the start and 0 at the end(1)
(b) (0|1)* between them to allow any number of 0s and 1s, i.e. 1(0|1)*0(1)
Answer: (a) ad, abcd, acbbd (b) 1(0|1)*0
Examiner tip: In (b) the string must be at least two symbols long (1 then 0), and the * allows zero or more middle symbols.

3Standard5 marks

A number format is defined using Backus-Naur Form (BNF):

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

(a) State which of these are valid <number>s: -07 +-5 5- 42 [2]

(b) Explain how the definition of <unsigned> allows numbers of any length. [1]

(c) Write BNF rules for a <name> that must start with a letter followed by any number of letters or digits. You may assume <letter> and <digit> are already defined. [2]

(a) -07 identified as valid(1)
(a) 42 identified as valid; deduct 1 mark for each invalid string (+-5 or 5-) also given as valid (minimum 0 for part (a))(1)
(b) <unsigned> is defined in terms of itself (recursion), so another digit can be added any number of times(1)
(c) <name> ::= <letter> | <letter><rest> (starts with a letter, optionally followed by more); allow an equivalent left-recursive form such as <name> ::= <letter> | <name><letter> | <name><digit> for both (c) marks(1)
(c) <rest> ::= <letter> | <digit> | <letter><rest> | <digit><rest> (recursive rule for any mix of letters and digits); accept any equivalent rules, e.g. <char> ::= <letter> | <digit> and <rest> ::= <char> | <char><rest>(1)
Answer: (a) -07, 42 (b) Recursive rule (c) <name> ::= <letter> | <letter><rest>; <rest> ::= <letter>|<digit>|<letter><rest>|<digit><rest>
Examiner tip: BNF has no * or loops: repetition can only be achieved by a rule that refers to itself.

4Standard4 marks

(a) State the time complexity of the following algorithm in terms of n. [1]

FOR i ← 1 TO n
  FOR j ← 1 TO n
    OUTPUT i * j
  ENDFOR
ENDFOR

(b) State the time complexity of a binary search on a sorted list of n items. [1]

(c) An algorithm with time complexity O(n²) takes 4 ms for n = 1000. Estimate the time it takes for n = 3000. Show your working. [2]

(a) O(n²)(1)
(b) O(log n)(1)
(c) n is multiplied by 3, so time is multiplied by 3² = 9(1)
(c) 4 × 9 = 36 ms(1)
Answer: (a) O(n^2) (b) O(log n) (c) 36 ms
Examiner tip: For O(n²), multiplying the input size by k multiplies the time by k², not by k.

5Hard6 marks

A Turing machine has the transition table below. Symbols are 0, 1 and _ (blank). The tape is blank on both sides of the input. The head starts on the leftmost symbol of the input in state q0. H is the halting state. Each rule is (new state, symbol written, direction).

State	Read 0	Read 1	Read _
q0	(q0, 0, R)	(q0, 1, R)	(q1, _, L)
q1	(H, 1, R)	(q1, 0, L)	(H, 1, R)

(a) The tape initially holds 1011. Give the tape contents when the machine halts. [1]

(b) State what the machine does to the binary number on the tape. [1]

(c) State the number of transitions the machine makes on the input 1011, including the one that enters H. Show your working. [2]

(d) Explain why a Turing machine is a useful model of computation. [2]

(a) 1100(1)
(b) Adds 1 to the number (increments it)(1)
(c) State q0 makes 5 transitions (4 moves right over the digits and 1 on the blank)(1)
(c) State q1 makes 3 transitions (1→0, 1→0, then 0→1 and halt), giving 8 in total; accept any correct trace showing all 8 transitions with total 8 for both (c) marks; 8 with no working scores 1 mark(1)
(d) It is a simple abstract/formal model (tape, read/write head, states, transition rules) that is independent of any hardware or programming language(1)
(d) Any problem that can be solved by an algorithm can be solved by a Turing machine, so it is used to define/reason about what is and is not computable; accept: a Universal Turing machine can simulate any other Turing machine given its description, which is the basis of the stored-program computer / interpreter(1)
Answer: (a) 1100 (b) Adds 1 (c) 8 (d) A simple, hardware-independent model of anything computable
Examiner tip: Count every transition, including the one on the blank and the final one that writes and halts.

6Standard4 marks

(a) State what is meant by the halting problem. [1]

(b) State the significance of the halting problem for computer scientists. [1]

(a) Determining, for any given program and input, whether the program will eventually halt or run forever(1)
(b) It shows that some problems cannot be solved by a computer / are non-computable (it has been proved that no general algorithm can solve the halting problem); accept: there are problems that no algorithm can solve; NE: 'some programs never stop'(1)
(c) Intractable: an algorithm exists, but there is no polynomial-time (or better) solution, so it takes an unreasonable amount of time for all but small inputs; accept e.g. exponential time(1)
(c) Unsolvable/non-computable: no algorithm can exist that solves every case, however much time or memory is available(1)
Answer: (a) Deciding whether any program halts on a given input (b) Proves some problems cannot be computed (c) Intractable = solvable but impractically slow; unsolvable = no algorithm exists
Examiner tip: Contrast the two ideas clearly: intractable is about time, unsolvable is about impossibility.

7Hard5 marks

The FSM below has start state A, which is also the only accepting state. The input alphabet is {0, 1}.

(a) State whether each input is accepted: 1001 and 0111. [2]

(b) Write a regular expression for the strings accepted by the FSM. [2]

(c) Explain why an FSM cannot be used to recognise the language of strings with n 0s followed by exactly n 1s for any n. [1]

(a) 1001 accepted (two 1s, finishes in A)(1)
(a) 0111 not accepted (three 1s, finishes in B)(1)
(b) Correct pattern for a pair of 1s with any number of 0s between them, e.g. 10*1(1)
(b) Fully correct expression that also allows 0s before/after and any number of pairs (including none), e.g. 0*(10*10*)* or (0|10*1)*; accept any equivalent expression that matches exactly the strings with an even number of 1s(1)
(c) An FSM has a fixed, finite number of states (no other memory), so it cannot remember/count an unbounded number of 0s to match against the 1s(1)
Answer: (a) 1001 accepted, 0111 rejected (b) 0*(10*10*)* (or equivalent, e.g. (0|10*1)*) (c) Finite memory cannot count unlimited 0s
Examiner tip: Describe the language first (an even number of 1s) and then build the regex from it.

Still losing marks on this topic?

Book a free introductory session and we'll find exactly which step is costing you.

Book a free intro