OCR A-Level Computer Science: Computational Thinking

The following regular expression and grammar were written for this exercise.

This question has three parts.

(a) Regular expressions. A programming language allows a variable name (identifier) to be: a single letter, followed by zero or more characters each of which is a letter, a digit or an underscore (_).

(i) Write a regular expression that matches exactly the valid identifiers described above. You may use a character class such as [a-zA-Z] for "any letter" and [0-9] for "any digit". [2 marks]

(ii) A different regular expression, over the alphabet {0, 1}, is supplied:

1(0|1)*0

State, for each of the three strings below, whether it matches the supplied regular expression 1(0|1)*0, giving a one-line reason for each: 1010, 1101, 0110. [2 marks]

(b) Backus-Naur Form. The following original BNF grammar defines an unsigned integer:

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

(i) State, with a reason, whether each of the strings 507, 3.5 and the empty string is a valid <unsigned-int>. [2 marks]

(ii) Give a step-by-step derivation of the string 507 starting from the symbol <unsigned-int>, naming the rule used at each step. [3 marks]

(c) Abstraction and decomposition. A team is building a sat-nav route-planning app. Explain how abstraction and how decomposition would each be applied to this problem, making the distinction between the two clear. [3 marks]

The following Turing machine was designed for this exercise.

A single-tape Turing machine processes a binary string written on its tape. The tape alphabet is {0, 1, _} where _ is the blank symbol. The machine has two states, q0 (the start state) and qHalt. It starts in q0 with the read/write head over the leftmost symbol of the string. Its transition function is:

Current state	Read	Write	Move (L/R)	Next state
q0	0	1	R	q0
q0	1	0	R	q0
q0	_	_	L	qHalt

The machine is started on the tape 1 0 0 1 (with blank cells either side), head over the leftmost 1.

(a) Trace the execution of the machine. Show, as a table, the tape contents (mark the head position with brackets, e.g. [1]), the current state, and the rule applied at each step, until the machine halts. [6 marks]

(b) State the final string left on the tape, and state in one sentence what the machine computes for a general binary input. [3 marks]

The following finite state machine was designed for this exercise.

A deterministic finite state machine (FSM) acting as an acceptor over the input alphabet {0, 1} has two states, E and O. E is the start state and the only accepting (final) state. Its state-transition table is:

Current state	Input 0	Input 1
→ * E	E	O
O	O	E

(→ marks the start state and \* marks the accepting state.)

(a) For each of the four strings below, trace the machine and state whether it is accepted or rejected: 101, 1110, 1010, and the empty string. Show the sequence of states entered for at least the first two. [4 marks]

(b) Describe in words the language (the set of strings) that this machine accepts. [2 marks]

The following grammar was written for this exercise.

A BNF grammar defines an unsigned integer as one or more decimal digits:

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

(a) Extend this grammar by adding the rules needed to define a new symbol <signed-int> that is an unsigned integer optionally preceded by a single + or - sign (so 42, +42 and -7 are all valid <signed-int>s, but --5 and a lone + are not). Write the new rule(s) in BNF; do not change the two existing rules. [3 marks]

(b) The rule <unsigned-int> ::= <digit> | <digit> <unsigned-int> uses recursion (it refers to itself). Explain how recursion in BNF is used to express repetition — a sequence of one or more digits — given that BNF has no explicit "repeat" operator. [2 marks]

The following algorithm was written for this exercise.

A naive recursive function computes the nth Fibonacci number:

function fib(n)
    if n <= 1 then
        return n
    else
        return fib(n - 1) + fib(n - 2)
    endif
endfunction

This is an example of thinking ahead. Computing fib(5) re-computes fib(3) twice, fib(2) three times, and so on — the same sub-problems are solved over and over.

Explain how caching (memoisation) could be applied to fib, describing what is stored and when it is reused, and state the effect this has on the amount of repeated work. [4 marks]

Some languages can be recognised by a finite state machine (FSM), but others cannot and require a more powerful model of computation.

Consider the language of all strings of the form $a^n b^n$anbn — that is, some number of as followed by the same number of bs (for example ab, aabb, aaabbb).

Explain why a finite state machine cannot recognise this language, and name a more powerful model of computation that can. [3 marks]