Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMPSCI 350
City COMPUTER SCIENCE
Mathematical Foundations of Computer Science
(Time allowed: TWO hours) NOTE: 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 COMPSCI 350 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 [25 marks] 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. [13 marks] (b) Prove that your construction is correct, that is, that the machine does indeed decide L. [12 marks] Question 3: Answer the following: (a) Given a language L over alphabet Σ, let the prefix set of L be Prefix(L) = {x ∈ Σ∗ | x is a prefix of some y ∈ L}. Show that the class of Turing-recognisable languages is closed under the prefix operation. [13 marks] (b) Show that the class of Turing-recognisable languages is not closed under the operation ∩, where ∩(A,B) = A ∩B. [12 marks] Page 2 of 3 COMPSCI 350 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}. [25 marks] 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? [5 marks] b) Is Lg,3 undecidable? Justify your answer. [20 marks] Question 6: Answer the following: a) State Rice’s Theorem. [5 marks]
b) Is the language {〈M〉 | M is a Turing machine with less than 100 states} undecidable? Justify your answer. [10 marks] c)
Can we apply Rice’s Theorem to the language {〈M〉 | M stops on the input 101}? Justify your answer. [10 marks]
Question 7: (a) Define the complexity function K. [5 marks] (b) Let x ∈ {0, 1}∗.
Give a condition equivalent to K(x) ≤ |x|− 1. Justify your answer. [10 marks] (c) Is the set {x ∈ {0, 1}∗ | K(x) ≤ |x|− 1}
Turing recognisable? Justify your answer. [5 marks] (d) Is the set {x ∈ {0, 1}∗ | K(x) ≤ |x|− 1} Turing decidable?
Justify your answer. [5 marks] Page 3 of 3