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 2021-2022

Computer Science

Theory 3 (THE3)

(1)  [8 marks]

Consider the unrestricted grammar G = ({S}, {a, b, c}, S, P) where P consists of the following productions:

S  →   aSbc | ^

bc →   cb

cb → bc

Precisely deine L(G), the language generated by G.

Hint: write #x (w) for the number of occurrences of a symbol x in a string w .

(2)  [20 marks]

Let M be the Turing machine with state set Q = {q0 , . . . ,q5 , ha , hr }, input alphabet = {a}, tape alphabet T = {a, , X}, initial state q0 , and the following transition

function 6:

(Remember that unspeciied transitions go to the reject state hr .)

(i)  [8 marks] Draw a transition diagram for M .

(ii)  [6 marks] Trace the computation of M on input aaaa, that is, give the tran-sition sequence starting with the coniguration q0 aaaa.

(iii)  [6 marks] Precisely specify L(M), the language accepted by M .

(3)  [12 marks]

Consider the emptiness problem (EP):

Input: A Turing machine M .

Question:  Is L(M) empty?

Show that the emptiness problem is undecidable, by reducing the membership prob- lem for semidecidable languages (MP) to EP.

(4)  [8 marks]

Given a Turing machine M, let H(M) be the set of input strings on which M halts. Show that if H(M) is decidable, then L(M) is also decidable.

b/b S

(i)  [4 marks] Give a transition sequence containing the maximum number of tran- sitions for an input of length 3.

(ii)  [4 marks] Give the function τM : N → N, the time complexity of M . (iii)  [2 marks] Give the function sM : N → N, the space complexity of M .

(9)  [10 marks]

Given functions f, g : N → N, the function f + g : N → N is deined by (f + g)(n) = f(n) + g(n).

Now consider functions f/ , g/ : N → N such that f ∈ O(f/ ) and g ∈ O(g/ ). Show that f + g ∈ O(f/ + g/ ).