COMP4141 Theory of Computation FINAL EXAM — Term 1, 2022

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

Question 1

(10 marks)

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

(a) {0n 1m : n, m e N and n - m < 2022} (b) {0n 1m : n, m e N and nm < 2022}

(5 marks) (5 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

(10 marks)

Recall from Assignment 1, the function rev that reverses a word. For a language L = x*, define the language mirror(L) as the language:

mirror(L) := {w rev(w) : w e L}

(a) Prove that if L is regular then mirror(L) is context-free.                             (5 marks)

(b) Show that there is a context-free language L such that mirror(L) is not context-free.

(5 marks)

Question 3          (10 marks)

Recall from lectures the Myhill-Nerode equivalence relation ●L, defined for a lan- guage L = x*, as:

w ●L v    if and only if    for all z e x*: wz e L - vz e L; and the equivalence classes:

[w]L  = {v e x*  : v ●L w}.

Prove that if L is regular then [w]L  is regular for all words w e x* . Hint: Consider a minimal automaton for L.

Question 4

Let x = {0, 1} and consider the following context-free grammar:

G = (V, x, R, S) where:

· V = {S, T}

· R is defined as:

S   >  0T  I  T0  I e

T   >   1S  I  S1

and the following regular expression:

E = (01 u 10)*

(a) Prove that L(G) /= L(E)

(b) Prove that L(E) /= L(G)

(10 marks)

(5 marks)

(5 marks)

Question 5                 (10 marks)

A function f : x* > r* is computable if there is a Turing Machine M which, on input x e x* halts with f (x) on the tape.

Prove that f : x* > r* is computable if and only if

Lf  = {(x, f (x))  : x e x* }

is recursively enumerable.

Question 6             (10 marks)

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

(a)


DFA INc工usIОN

Input: A Turing Machine M and a DFA D

Question: Is L(D) = L(M)?


(5 marks)

(b)

BPP MEMBERsHIo

Input: A Non-deterministic Turing Machine M that halts in polynomial time on all runs of all inputs

Question: Is it the case that for all inputs: either at least of all runs are accepting, or at least of all runs are rejecting?


(5 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)

The Surveillance Problem can be described as follows. A museum contains a number of rooms and can purchase a number of cameras to surveil these rooms. Each camera can surveil multiple rooms and rooms can be surveiled by multiple cameras (this information is given by a monitoring relation). The goal is to monitor all the rooms with as few cameras as possible. Formally stated as a decision problem:

SuRvEI工工ANcE PRОB工EM

Input: A set C of cameras; a set R of rooms; a monitoring relation M = C × R; and an integer k

Question: Is there a subset C兮 = C such that:

· IC兮 I C k, and

· R = M(C兮 ) = {r : (c, r) e M for some c e C兮 }?

Show that the Surveillance Problem is NP-complete.

Question 8

(10 marks)

In the sport of Rogaining the challenge is to visit checkpoints to accrue a score in a limited timeframe. Checkpoints have different values largely dependent on their accessibility – checkpoints that are more difficult to reach usually have a higher value. The goal of the competitors is to choose a route that maximizes the value of the checkpoints seen without exceeding the allocated time (not all checkpoints have to be visited, but you can only visit a checkpoint once). Formally, as a decision problem:

RОcAININc

Input: A set V = {v(1), . . . , v(n)} of n checkpoint values; an n × n table {t(i, j)} where t(i, j) indicates the time to get from checkpoint i to checkpoint j; an integer T; and an integer V

2023-04-28