AQA A-Level Computer Science: Theory of Computation
6 exam-style questions with full mark schemes and model answers. Write your own answer and the AI examiner marks it against the mark scheme.
The following finite state machines were designed for this exercise.
Machine A is a deterministic finite state machine (an acceptor) over the input alphabet {0, 1}. It has three states S0, S1 and S2. S0 is the start state and S2 is the only accepting (final) state. Its transition function is given by the partially completed state-transition table below:
| Current state | Input 0 | Input 1 |
|---|---|---|
| → S0 | S1 | S0 |
| S1 | S1 | (i) |
| * S2 | (ii) | S0 |
The missing entries are: from S1 on input 1 the machine moves to the accepting state S2; from S2 on input 0 it moves to S1.
(a) Copy and complete the table by giving the next state for entries (i) and (ii), then trace Machine A on the input string 01101 and on the input string 0100, showing the sequence of states entered, and state whether each string is accepted or rejected. [6 marks]
(b) Describe in words the language (the set of strings) that Machine A accepts. [3 marks]
Machine B is a Mealy machine over {0, 1} with two states A (start) and B. Each transition is labelled input / output. Its transitions are: A on 0 outputs 0 and stays in A; A on 1 outputs 1 and goes to B; B on 0 outputs 1 and goes to A; B on 1 outputs 0 and stays in B.
(c) Give the output string Machine B produces for the input string 0110, and state in one sentence what Machine B detects about its input. [3 marks]
The following Turing machine was designed for this exercise.
A single-tape Turing machine adds 1 to a binary number written on its tape (for example, the binary number for 11 should become the binary number for 12). The tape alphabet is {0, 1, □}, where □ is the blank symbol. The machine has states q0, q1 and qHalt; it starts in state q0 with the read/write head over the leftmost digit of the number. Its transition function is:
| State | Read | Write | Move | Next state |
|---|---|---|---|---|
| q0 | 0 | 0 | R | q0 |
| q0 | 1 | 1 | R | q0 |
| q0 | □ | □ | L | q1 |
| q1 | 0 | 1 | L | qHalt |
| q1 | 1 | 0 | L | q1 |
| q1 | □ | 1 | L | qHalt |
The machine is started on the tape 1 0 1 1 (with blanks 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. [7 marks]
(b) State the final binary number left on the tape, and confirm that the machine has computed the correct result. [2 marks]
The following expression was written for this exercise.
Consider the infix arithmetic expression:
( 8 + 2 ) * 5 - 3
(a) Convert this expression to Reverse Polish Notation (postfix). Show your working by tracing the conversion with an operator stack, giving the output so far and the stack contents as each token is processed, as a table. [4 marks]
(b) Evaluate your RPN expression using a value stack, showing the stack contents after each token, and state the final result. [2 marks]
A software company proposes to write a single tool, WillHalt, that takes any program P and any input I for that program, and always prints "halts" if running P on I would eventually stop, or "loops forever" if it would run forever — without ever itself getting stuck.
(a) State the name of the problem the company is trying to solve, and state whether it is decidable or undecidable. [1 mark]
(b) Explain why no such program WillHalt can exist. Your explanation should outline the contradiction that arises if it did. [4 marks]
The following notation was written for this exercise.
(a) A regular expression over the alphabet {a, b} is:
a(a|b)*b
State in words the set of strings this regular expression matches. [2 marks]
(b) A programmer needs to define the syntax of balanced (matched) parentheses — strings such as (), (()) and ()() — and finds that no regular expression can do this. Name the kind of grammar notation that can define this language, and explain in one or two sentences why it can express something a regular expression cannot. [2 marks]
In computational theory a clear distinction is drawn between a state and a transition in a finite state machine.
(a) Define what is meant by a state and by a transition. [2 marks]
(b) Give one example of each, drawn from any finite state machine you choose. [1 mark]