COMP4141 Theory of Computation FINAL EXAM — Term 1, 2021

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Theory of Computation (COMP4141)

FINAL EXAM — Term 1, 2021

Question 1

(12 marks)

Are the following languages regular, context-free but not regular, or not context-free? Justify your answers.

(a)  {0n 1m   : n, m > 1 and n = m + 2k for some k e Z} (b)  {0n 1m   : n, m > 1 and n = 2 + mk for some k e Z}

(6 marks) (6 marks)

Remark

Partial marks can be obtained for a suboptimal answer (e.g.  showing the lan- guage is context-free without determining if it is regular)

 

Question 2                                                                                                    (8 marks)

For a language L C E*, define the language dbl(L) as the language:

dbl(L) := {ww : w e L}

Prove or disprove: If L is regular then dbl(L) is regular.

Question 3                                                                                                  (12 marks)

For a language L C E*, define the language L ÷ 2 as the language:

L ÷ 2 := {w e E* :  there exists x e E* with lwl = lxl and wx e L}.

(a) Show that if L is regular then L ÷ 2 is regular.                                           (4 marks)

(b) Show that there is a non-regular language L such that L ÷ 2 is regular.  (4 marks)

(c) Show that there is a context-free language L such that L ÷ 2 is not context-free. (Hint: Consider L = {0i1j2j33i  : i, j e N})                                                    (4 marks)

Question 4            (8 marks)

Show that if L is recursively enumerable then L* is recursively enumerable.

Question 5

Consider the following context-free

G1 = (V, E, R1, S) where:

● V = {S, T}

● E = {a, b}

● R1 is defined as:

S   -  aS  l  ST  l  e

T   -  aTb  l  Tb  l  b

Prove that L(G1)  L(G2).

(8 marks)

grammars:

G2 = (V, E, R2, S) where:

● V = {S, T}

● E = {a, b}

● R2 is defined as:

S   -  aS  l  TS  l  e  T   -  aTb  l  Tb  l  b

(8 marks)

Question 6             (12 marks)


Are the following decision problems decidable, recursively enumerable but undecid- able, or not recursively enumerable? Justify your answers.

(a)

Input: A Turing Machine M

Question: Does there exist an input x such that M, on input x, halts in at most 161 steps?  (6 marks) 

(b)

Input: A Turing Machine M and a polynomial p

Question: Is it the case that for all inputs x: M, on input x, halts in at most p(lxl) steps?   (6 marks)

 


Remark

Partial marks can be obtained for a suboptimal answer (e.g.  showing the lan- guage is recursively enumerable without determining if it is decidable)



Question 7            (10 marks)

(a) Suppose that M = (Q, E, r, 6, q0, qacc, qrej) is a Turing Machine that uses at most f (lxl) space on input x (on a separate working tape if appropriate).  Show that there exists a Turing Machine M/ with L(M) = L(M/) that uses at most f (lxl)/2 space on input x. (Hint: Consider using a larger tape alphabet)                    (6 marks)

Prove that

L =  n  SPACE(log(nk)).

keN

(4 marks)

Question 8                   (10 marks)


The Four colour theorem states that every planar graph can be coloured with 4 colours.  One consequence of this is that four colours suffice to colour any map of countries. However, for practical purposes it can sometimes be useful to colour a cer- tain set of countries (e.g. the Commonwealth) with the same colour. This motivates the following problem:


P工…|…R 4-Bo工ouRr|c wrrH CoMMo|wE…工rH

Input: A planar graph G and a subset C of vertices

Question: Is it possible to colour G with 4 colours such that adjacent vertices have different colours, and every vertex in C has the same colour?


Show that P工…|…R 4-Bo工ouRr|c wrrH CoMMo|wE…工rH is NP-complete.


Question 9        (12 marks)

The chromatic number of a graph G, x(G) is the smallest natural number k such that G can be coloured with k colours such that adjacent vertices do not have the same colour.

Consider the following decision problem:


CHRoMATIC N对MBER

Input: A graph G and an integer k

Question: Is x(G) = k?


(a) Show that CHRoMATIC N对MBER is NP-hard.

(b) Show that CHRoMATIC N对MBER is coNP-hard.

(c) Show that CHRoMATIC N对MBER is in PNP .

(4 marks) (4 marks)

(4 marks)


Remark

Partial marks can be obtained by showing that CHRoMATIC N对MBER is in E2P


Question 10              (8 marks)

Show that the following problem is NL-complete:


ENFA

Input: An NFA A

Question: Is L(A) = O?



2023-04-28