COM00023I Theory 3 2020-2021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COM00023I
BEng, BSc, MEng and MMath Degree Examinations 2020-2021
Computer Science
Theory 3 (THE3)
(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]
Deine the language L(G) in words.
(iii) [4 marks]
Deine L(G) by a regular expression.
(iv) [4 marks]
Deine 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 T = {a, b, 
, X}, initial state q0 , and the following transition function 6:
q0 
(q1 , 
, R)
(Remember the convention that unspeciied 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 coniguration 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 .
(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 t N does the following Turing machine M compute?
1/1 R
/
L
q5 
/
R
q6 
/1 L ha
1/
L
(ii) [5 marks]
Consider the following Turing machine M :
1/1 R
1/1 L
1/1 L q3
Is the computed function fM : N t N total or not? Explain your answer.
(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 coniguration on input w?
Existential halting problem (EHP)
Input: A Turing machine M .
Question: Is there an input string on which M reaches a halting coniguration? 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}:
a/a R
b/b R b/b R
q0 
/
R
/
L 
/
L 
/
L
q5
/
S 
ha 
/
S q4
a/a L
b/b L
a/
L
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 .
(6) [10 marks]
Consider the following nondeterministic Turing machine N with input alphabet {a}:
a/a R a/a L a/a R
a/a R
(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 satisiable 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. Now consider the following decision problem:
DNF-satisiability problem (DNF-Sat)
Input: A boolean expression D in disjunctive normal form.
Question: Is D satisiable?
Sketch a proof that DNF-Sat is in P.
Hint: show that there is a cheap way to check whether a single conjunction of literals is satisiable. Then describe a Turing machine which solves DNF-Sat based on this check, and explain why the machine’s time complexity is a polynomial.
2023-02-19