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