Module Code
COM00023I
BEng, BSc, MEng and MMath Degree Examinations 2020-2021
Department: Computer Science
Title: Theory 3 (THE3)
Time Allowed: 24 hours (NOTE: Late papers will not be marked)
Time Recommended: TWO hours
Allocation of Marks:
Q1: 14 marks; Q2: 18 marks; Q3: 10 marks; Q4: 12 marks; Q5: 12 marks; Q6: 10 marks; Q7: 12 marks; Q8: 12 marks
Instructions:
• Answer all questions.
• Submit your answers to the Department’s Teaching Portal as a single PDF file.
• If a question is unclear, answer the question as best you can, and note the assump- tions you have made to allow you to proceed.
• Do not use colour: use black-on-white only.
• Start each top-level question on a new page.
Page 1 of 6
A Note on Academic Integrity
We are treating this online examination as a time-limited open assessment, and you are therefore permitted to refer to written and online materials to aid you in your answers.
However, you must ensure that the work you submit is entirely your own, and for the whole time the assessment is live you must not:
• communicate with departmental staff on the topic of the assessment
• communicate with other students on the topic of this assessment
• seek assistance with the assignment from the academic and/or disability support services, such as the Writing and Language Skills Centre, Maths Skills Centre and/or Disability Services. (The only exception to this will be for those students who have been recommended an exam support worker in a Student Support Plan. If this applies to you, you are advised to contact Disability Services as soon as possible to discuss the necessary arrangements.)
• seek advice or contribution from any third party, including proofreaders, online fora, friends, or family members.
We expect, and trust, that all our students will seek to maintain the integrity of the assessment, and of their award, through ensuring that these instructions are strictly fol- lowed. Failure to adhere to these requirements will be considered a breach of the Academic Misconduct regulations, where the offences of plagiarism, breach/cheating, collusion and commissioning are relevant: see AM1.2.1. (Note this supersedes Section 7.3 of the Guide to Assessment).
Page 2 of 6
(1) [14 marks]
Consider the grammar G = ({S}, {a, b}, S, P ) where P consists of the following productions:
S → Sb|aaa ab → ba
(i) [2 marks]
Give a derivation of the string ababa.
(ii) [4 marks]
Define the language L(G) in words.
(iii) [4 marks]
Define L(G) by a regular expression.
(iv) [4 marks]
Define L(G) by a context-free grammar.
(2) [18 marks]
Let M be the Turing machine with state set Q = {q0, . . . , q4, ha, hr}, input alphabet Σ = {a,b}, tape alphabet Γ = {a,b,∆,X}, initial state q0, and the following transition function δ:
δ∆abX
(q2,X,L) (q2,X,L) (q3,X,R) (q4,b,R) (q4,X,R)
(Remember the convention that unspecified transitions go to the reject state hr.)
(i) [4 marks]
Draw a transition diagram for M.
(ii) [6 marks]
Trace the computation of M on input aabbb, that is, give the transition se- quence starting with the configuration q0∆aabbb.
(iii) [2 marks]
Give an input string ending in b that is not accepted by M .
(iv) [6 marks]
Precisely specify L(M), the language accepted by M.
Page 3 of 6
(q1, ∆, R)
(q1,a,R) (q2,X,L)
q0
q1
q2 (q4,∆,R) (q3,X,R) q3
q4 (ha,∆,S)
(3) [10 marks]
This question is about numeric functions. Assume that a natural number n ≥ 0 is
represented by the string 1n (where 10 = Λ).
(i) [5 marks]
What partial function fM : N → N does the following Turing machine M compute?
1/1 R
q ∆/∆R q 1/1R q 1/1R q 1/1R q
01234
q5 ∆/∆R q6 ∆/1L ha 1/∆ L
(ii) [5 marks]
Consider the following Turing machine M:
q ∆/∆R q 1/1R q 012
1/1 L
∆/∆ L
∆/∆ L
q3
Is the computed function fM : N → N total or not? Explain your answer.
ha
1/1 L
Page 4 of 6
(4) [12 marks]
Consider the following decision problems:
Halting problem (HP)
Input: A Turing machine M and a string w ∈ Σ∗.
Question: Does M reach a halting configuration on input w? Existential halting problem (EHP)
Input: A Turing machine M.
Question: Is there an input string on which M reaches a halting configuration?
Show that the existential halting problem is undecidable, by reducing HP to EHP.
(5) [12 marks]
Consider the following Turing machine M with input alphabet {a,b}: b/b R
b/b R 0123
a/a R
q ∆/∆R q
q5 ∆/∆S ha ∆/∆S q4
a/a R
∆/∆ L
q
q
∆/∆ L
∆/∆ L
a/a L b/b L
(a) [6 marks] What function fM : {a,b}∗ → {a,b}∗ does M compute? (b) [4 marks] Give the function τM, the time complexity of M.
(c) [2 marks] Give the function sM, the space complexity of M.
Page 5 of 6
a/a R b/b R
a/∆ L b/∆ L
(6) [10 marks]
Consider the following nondeterministic Turing machine N with input alphabet {a}:
a/aR a/aL a/aR
q ∆/∆R q a/aL q a/aR q ∆/∆S
0 1 2 3 ha
(i) [4 marks] Give a transition sequence containing the maximum number of tran-
sitions on input aaa.
(ii) [4 marks] Give the function τN, the time complexity of N.
(iii) [2 marks] Give the function sN, the space complexity of N.
(7) [12 marks]
(i) [6 marks] Show by induction that 2n ∈ O(n!). (ii) [6 marks] Show that n4 − 2n ̸∈ O(n3).
(8) [12 marks]
A boolean expression D is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals. For example,
(¬x1 ∧x2 ∧x1) ∨ (x2 ∧ ¬x3) ∨ (¬x2 ∧x3)
is in disjunctive normal form. An expression is satisfiable if there is an assignment of truth values to variables making the expression true. For example, the assignment
x1, x2 → true, x3 → false makes the above expression true. following decision problem:
DNF-satisfiability problem (DNF-Sat)
Input: A boolean expression D in disjunctive normal form.
Question: Is D satisfiable?
Sketch a proof that DNF-Sat is in P.
Now consider the
Hint: show that there is a cheap way to check whether a single conjunction of literals is satisfiable. Then describe a Turing machine which solves DNF-Sat based on this check, and explain why the machine’s time complexity is a polynomial.
End of examination paper Page 6 of 6