A06472 No calculator permitted in this examination
THE UNIVERSITY OF BIRMINGHAM
THIS PAGE TO BE REPLACED BY OFFICE
06 05934
Models of Computation
May 2015 1.5 hours
[Answer all questions.]
Turn Over
No calculator
1. [29%] This question is about regular languages and finite-state automata.
(a) Give a regular expression for the language over the alphabet {a, b} consisting of
all words in which a occurs an even number of times.
[7%]
(b) Give a deterministic finite state automaton for this language.
[7%]
(c) Let L be the language over the alphabet {a, b} consisting of all words in which a
and b occur an equal number of times. Using the pumping lemma, show that L
is not regular.
[8%]
(d) Here are two deterministic finite state automata.
1
2
3
4
0
5
6
10 8
9
7
a
b
a,b
a,b
b
a
b
a
b
a b
a,b
a
a
b
a,b
a,b
Give a bisimulation to show that they recognize the same language.
[7%]
A06472 – 2 – Turn Over
No calculator
2. [22%] This question is about decidability.
You are an employee of Ellipse Ltd, which sells an integrated development environment
(IDE) for Java programmers. The IDE is itself written in Java. A new version is being
developed.
(a) The manager says to you: “Create a button that determines whether, in the Java
file selected by the user, there are two different declarations of variables with the
same name.” (For example, if there are two different lines declaring int i, then
the button will print Yes.) Can this be accomplished? Explain your answer.
[7%]
(b) The manager says to you: “Create a button that determines whether the Java
method selected by the user may be called with some argument that will cause an
exception to be thrown.” Can this be accomplished? Explain your answer.
[7%]
(c) The manager has decided that the new IDE will be written not in Java but in a
different programming language. Does that make a difference to your answers?
Explain.
[8%]
A06472 – 3 – Turn Over
No calculator
3. [21%] This question is about two-tape Turing machines.
Look at the two-tape machine below.
a
b
a,b
a
b
Right aux
Right main
Read main
Write aux b
Write aux a
Left aux
Read aux
Right aux
Stop
Read aux
Write main a
Right main
Write main b
0
1
2 3
4
5
6
7
8
9
10
11
12
⎵
⎵
⎵
Initially, the main tape contains a nonempty block of a’s and b’s with the rest of the
tape blank, and the head over the leftmost character. The auxiliary tape is initially
blank.
(a) If the initial block is ab, show the first five execution steps. (Altogether 25 steps
are performed before the machine halts.) After each step, you should show the
current state, the contents of each tape and the position of each head. [7%]
(b) What does this machine do in general?
[7%]
(c) What is the complexity of this machine, in terms of the length n of the block that
is initially on the main tape? Explain your answer briefly.
[7%]
A06472 – 4 – Turn Over
No calculator
4. [14%] This question is about NP .
In the popular puzzle Sudoku, a square grid of n2×n2 small squares is displayed, divided
into n × n square subgrids each consisting of n × n small squares, and partially filled
with numbers in the range 1 to n2 inclusive. The task is to fill all the remaining squares
with numbers in the range 1 to n2 inclusive, in such a way that in each column, each
row and each subgrid, every number appears precisely once. Here is an example with
n = 3.
Partially filled grid Solution
5 3 7
6 1 9 5
9 8 6
8 6 3
4 8 3 1
7 2 6
6 2 8
4 1 9 5
8 7 9
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
(a) Not every partially filled grid is solvable. Explain why solvability of a partially filled
grid is in NP .
[7%]
(b) It has been shown that this problem is NP-complete. Explain what that means.
[7%]
A06472 – 5 – Turn Over
No calculator
5. [14%] This is a question about λ-calculus with arithmetic. The syntax of terms is
given by the following grammar.
M ::= x |MM | λx.M | n |M +M
where x ranges over variables and n over the integers.
(a) Here is a term:
(λx. λy. x y) (λx. x+ y) (3 + 1)
By applying β-reductions and δ-reductions, reduce this term to normal form.
[7%]
(b) Let the syntax of types be given by
A ::= int | A→ A
where int is the type of integers.
For each natural number n we define a type An as follows:
A0 = int
An+1 = An → int
Define, for each natural number n, a closed term that has type An and no other
type. [7%]
A06472 – 6 – End of Paper