NOTE:
COMPSCI 350 THE UNIVERSITY OF AUCKLAND
SEMESTER ONE 2019 Campus: City
COMPUTER SCIENCE Mathematical Foundations of Computer Science
(Time allowed: TWO hours)
Attempt to answer Question 1 and three other Questions in your answer script book.
You may use without proof any result proved in class; in such a case, indicate exactly the statement of the result (theorem, fact, example, corollary, etc.) you use.
Page 1 of 3
Question 1 For each of the following sentences write in your script book Y (YES) if the sentence is true or N (NO) if the sentence is false:
(a) The set of Turing-recognisable languages over {0, 1} is uncountably infinite.
(b) Some infinite Turing-recognisable languages are not Turing-decidable.
(c) ATM is not Turing-recognisable.
(d) There are problems that can be solved using the universal programming language Python that cannot be solved using standard Turing machines.
(e) If language A over alphabet Σ is not decidable, then neither is any language B over Σ such that A ⊆ B.
(f) The language {ε} is decidable.
(g) The complement of every Turing-recognisable language is Turing-recognisable.
(h) The latest D-Wave quantum computer is deterministic.
(i) If A ≤m B and B is decidable, then A is Turing-recognisable.
(j) The complements of some Turing-recognisable languages are Turing-recognisable.
infinite. equivalent to
Question 2: Answer the following:
(a) Design a Turing machine that decides the following language:
L = {w ∈ {0, 1}∗ | w contains contains at least one copy of a substring 02m12n+10, for some m ≥ 0, n ≥ 0}.
Give a formal description of the machine (by specifying the transition function in state diagram form), and show that your machine accepts 10 but rejects 110.
(b) Prove that your construction is correct, that is, that the machine does indeed decide L.
Question 3: Answer the following:
(a) Given a language L over alphabet Σ, let the prefix set of L be
Prefix(L)={x∈Σ∗ |xisaprefixofsomey∈L}.
Show that the class of Turing-recognisable languages is closed under
the prefix operation.
(b) Show that the class of Turing-recognisable languages is not closed under
the operation ∩, where ∩(A, B) = A ∩ B.
[25 marks]
[13 marks] [12 marks]
[13 marks] [12 marks]
COMPSCI 350
Page 2 of 3
Question 4: Show that the following languages are Turing-decidable:
(a) L = {〈A〉 | A is a DFA over the alphabet{0, 1} and L(A) only contains
strings even in length}.
(b) L = {〈A〉 | A is an NFA and L(A) contains exactly k strings},
where k ≥ 0 is a fixed number.
(c) L = {〈A〉 | A is a DFA over the alphabet{0, 1} and there exists k ≥ 0, L(A)
contains exactly k strings}.
Question 5: Let g be a computable function. For every natural n, define the language Lg,n = {〈M〉 | M has more than g(n) states}.
a) What is the language Lg,3 when g(n) = n2? b) Is Lg,3 undecidable? Justify your answer.
Question 6: Answer the following:
a) State Rice’s Theorem.
[25 marks]
[5 marks] [20 marks]
[5 marks]
[10 marks]
[10 marks] [5 marks]
[10 marks] [5 marks] [5 marks]
Question 7:
b) Is the language
{〈M 〉 | M is a Turing machine with less than 100 states} undecidable? Justify your answer.
c) Can we apply Rice’s Theorem to the language {〈M 〉 | M stops on the input 101}?
Justify your answer.
(a) Define the complexity function K .
(b) Let x ∈ {0, 1}∗ . Give a condition equivalent to K (x) ≤ |x| − 1.
Justify your answer.
(c) Is the set {x ∈ {0, 1}∗ | K (x) ≤ |x| − 1} Turing recognisable? Justify your answer.
(d) Is the set {x ∈ {0, 1}∗ | K(x) ≤ |x| − 1} Turing decidable? Justify your answer.
Page 3 of 3
COMPSCI 350