COM00002I
BEng, BSc, MEng, and MMath Degree Examinations 2019-2020
DEPARTMENT OF COMPUTER SCIENCE
Computability and Complexity
Time Allowed: ONE hour and THIRTY minutes Materials Supplied:
Green Booklet
Marking Scheme:
Questions are worth different marks
Instructions:
Candidates should answer all questions
Do not write on this booklet before the exam begins
Do not turn over this page until instructed to do so by an invigilator
Page 1 of 5
(1) [6 marks]
Consider the following pushdown automaton M with input alphabet {a,b,#} and
stack alphabet {A,B}:
b Λ/B a Λ/A
q0
# Λ/Λ
q1
a A/Λ aA/Λ q2
q3
b B/Λ
b B/Λ
Precisely define L(M), the language accepted by M. (Assume acceptance by empty stack.)
(2) [10 marks]
Consider the grammar G = ({S,A,B}, {a,b,#},S, P) where P consists of the following productions:
S→aAS|bBS| # Aa→aA Ba→aB Ab→bA Bb→bB A#→#a B#→#b
(i) [2 marks] Pick a string of length 5 in L(G) and show its derivation. (ii) [8 marks] Precisely define L(G), the language generated by G.
Page 2 of 5
(3) [20 marks]
Let M be the Turing machine with state set Q = {q0, . . . , q7, ha, hr}, input alphabet Σ = {a,b, #}, tape alphabet Γ = Σ ∪ {∆,X}, initial state q0, and the following transition function δ:
δ∆ab#X
(q1, ∆, R)
(q2, ∆, R) (q5, ∆, R) (q7, #, R)
q0
q1
q2
q3 (q4,X,L) (q3,X,R) q4 (q1,∆,R) (q4,a,L) (q4,b,L) (q4,#,L) (q4,X,L)
(q2,a,R) (q2,b,R) (q3,#,R)
(q5,a,R) (q5,b,R) (q6,#,R)
(q4,X,L) (q6,X,R)
(q7,X,R) (Remember that unspecified transitions go to the reject state hr.)
(i) [8 marks] Draw a transition diagram for M.
(ii) [6 marks] For each of the following strings, say whether it is accepted by M or
not:
– ab#aa
– ab#ab
(iii) [6 marks] Precisely define L(M), the language accepted by M.
(4) [10 marks]
This question is about numeric functions. Assume that a natural number n ≥ 0 is
represented by the string 1n (where 10 = Λ).
What function fM : N → N does the following Turing machine M compute?
q5
q6
q7 (ha,∆,S)
1/XR 1/1L 1/1R q ∆/∆R q ∆/∆L q X/1R q
0123
∆/1 R ha ∆/1 L q4
Page 3 of 5
∆/∆ S
Turn over
(5) [10 marks]
What partial function fM : {a,b}∗ → {a,b}∗ does the following Turing machine M compute?
b/b R
a/a R 0123
q ∆/∆R q
q a/aL q ha
b/b R
∆/∆ S
(6) [6 marks]
Give a countability argument why there are fewer semidecidable languages than languages that are not semidecidable.
(7) [14 marks]
Consider the following nondeterministic Turing machine M with input alphabet
{a, b, c}:
q ∆/∆R q c/cR q a/aR q 0123
c/c L b/b R q b/bL q a/aL
a/a L b/b L
a/a R b/b R c/c R
4 5 ha
(i) [2 marks] What is L(M), the language accepted by M?
(ii) [5 marks] Give a transition sequence for an input of length 3 containing the maximum number of transitions.
(iii) [5 marks] Give the function τM, the time complexity of M.
(iv) [2 marks] Give the function sM, the space complexity of M.
Page 4 of 5
(8) [6 marks]
Answer each of the following with “true” or “false”. You need not justify your answer.
(i) [3 marks] 2n ∈ O(n!) (ii) [3 marks] 3n ∈ O(2n)
(9) [6 marks]
(i) [3 marks] Let L1, L2 ⊆ Σ∗ be languages. What does it mean to say that L1 is
polynomial-time reducible to L2?
(ii) [3 marks] What does it mean that a language L is NP-hard?
(10) [12 marks]
A boolean expression C1 ∧ C2 ∧ · · · ∧ Cn is in conjunctive normal form (CNF) if each
conjunct Ci is a disjunction of literals.For example, (¬x1 ∨x2 ∨x4) ∧ (x3 ∨ ¬x3)
is in conjunctive normal form. An expression is a tautology if every assignment of truth values to variables makes the expression true. For example, the above expression is not a tautology because the assignment x1,x3 → true, x2,x4 → false makes it false. Now consider the following decision problem:
CNF-Tautology problem (CNF-Taut)
Input: A boolean expression C in conjunctive normal form.
Question: Is C a tautology?
Sketch a proof that CNF-Taut is in P. (Hint: show that a CNF expression is a tautology if and only if each disjunction of literals has a particular form; then describe a Turing machine which checks whether each conjunct has this form.)
END OF PAPER
Page 5 of 5