CS计算机代考程序代写 LAST NAME (please print)

LAST NAME (please print)

First name (please print)

Student Number

western university
department of computer science

CS3331: Foundations of Computer Science – Fall 2020
– Final Exam –

Saturday, Dec. 12, 2020, 2:00 – 5:00pm
Location: OWL

Instructor: Prof. Lucian Ilie

Upload your solutions in OWL by 5:30pm.
Approved accommodation: email to by 2:00pm + your approved time + 30min.

In either case, failure to do so will result in your exam being discarded; no exceptions.

This exam consists of 5 questions (6 pages, including this page), worth a total of 100 marks.
The exam is 180 minutes long and comprises 39% of your final grade.

For each questions, solve only part Vi, 0 ≤ i ≤ 3, where i = student number mod 4.
Failure to answer the correct version will result in your answer being discarded.

Vi =

(1) 20pt

(2) 20pt

(3) 20pt

(4) 30pt

(5) 10pt

Grade

CS3331 – Final Exam – Saturday, Dec. 12, 2020, 2:00 – 5:00pm 2

1. (20pt) Remember to solve only your version Vi; calculate correctly your i = student number mod 4.
Construct a deterministic Turing machine M that performs the action indicated at your Vi below. M starts
with the initial configuration (s,�w) and halts with the configuration (h,�w). Describe M using the macro

language (the one that looks like this: R�,a
�−→ aRbL¬�).

V0 : Σ = {a, b}; M replaces any occurrence of aba in the input with aca.
V1 : Σ = {0, 1}; M adds 2 to its input, seen as a binary number.
V2 : Σ = {a, b}; M moves the leftmost a (if any) to the end of the input, then closes the hole where a was.
V3 : Σ = {a, b, c}; M replaces the input with the number of a’s in the input, written in unary (using 1’s).

CS3331 – Final Exam – Saturday, Dec. 12, 2020, 2:00 – 5:00pm 3

2. (20pt) Describe in clear English a Turing machine that semidecides the language L given below:

V0 : L = { |M rejects at least two strings}
V1 : L = { |M accepts at least one string starting with a}
V2 : L = { |M accepts the empty string and at least one string of odd length}
V3 : L = { |M accepts at least two strings of different lengths}

CS3331 – Final Exam – Saturday, Dec. 12, 2020, 2:00 – 5:00pm 4

3. (20pt) Prove your answers to the questions below ((a) – 6pt, (b) – 5pt, (c) – 9pt: 3pt for each (i)-(iii)):

V0 : (a) Is it possible that L ∈ D and L ∩ ¬L 6∈ SD − D?
(b) If we modify an FSM to allow infinitely many states, then we can easily accept any language, e.g.,

we can build a path to accept every string in the language. That means, we can accept also non-SD
languages. Does this contradict Church’s thesis?

(c) Can the union L1 ∪ L2, for L1 ∈ SD, L2 ∈ ¬SD be in: (i) D, (ii) SD − D, (iii) ¬SD?
V1 : (a) Is it possible that L is regular and ¬(L ∩ ¬L) 6∈ SD − D?

(b) Is it possible to design a new mechanism (that would have a finite description) such that the languages
it accepts are precisely the non-SD languages, thus contradicting Church’s thesis?

(c) Can the intersection L1 ∩ L2, for L1 ∈ SD, L2 ∈ ¬SD be in: (i) D, (ii) SD − D, (iii) ¬SD?
V2 : (a) Is it possible that L is context-free and L− ¬¬L 6∈ SD − D?

(b) Is it possible to define a new mechanism that uses a Turing Machine but accepts exactly when the
TM does not; such a mechanism would then accept languages such as ¬H, which is not in SD, thus
contradicting Church’s thesis?

(c) Can the difference L1 − L2, for L1 ∈ SD, L2 ∈ ¬SD be in: (i) D, (ii) SD − D, (iii) ¬SD?
V3 : (a) Is it possible that L 6∈ SD and L ∪ ¬L ∈ D?

(b) Let’s define a new class of languages, which is obtained as the closure of SD under complement. This
new class would strictly include SD, as it would include, for instance, ¬H. Does this contradict Church’s
thesis?

(c) Can the intersection L1 ∩ L2, for L1 ∈ ¬SD, L2 ∈ SD be in: (i) D, (ii) SD − D, (iii) ¬SD?

CS3331 – Final Exam – Saturday, Dec. 12, 2020, 2:00 – 5:00pm 5

4. (30pt) Consider an alphabet Σ such that all languages below are over Σ.

(i) (18pt) For each of the languages below, prove, without using Rice’s theorem, whether it is in D, SD − D,
or ¬SD. Explain first intuitively why you think it is in D, SD − D, or ¬SD, then prove your assertion
rigorously.

(ii) (12pt) Explain whether Rice’s Theorem applies or not to each of these languages.

V0 : (a) L1 = { |M1 accepts at least two strings and M2 rejects at least one string}
(b) L2 = { |M accepts only the string aba}
(c) L3 = a

V1 : (a) L1 = { |M1 accepts at least one string in a∗ and M2 rejects at least one string in b∗}
(b) L2 = { | |L(M)| ≤ 10}
(c) L3 = {ε}

V2 : (a) L1 = { |M1 accepts a and L(M2) is not empty}
(b) L2 = { |M accepts finitely many even-length strings}
(c) L3 = ∅

V3 : (a) L1 = { |M1 accepts at least one string and M2 rejects at least one string}
(b) L2 = { |M accepts two palindromes and nothing else}
(c) L3 = {ab}

CS3331 – Final Exam – Saturday, Dec. 12, 2020, 2:00 – 5:00pm 6

5. (10pt) Answer your version of the PCP question below:

V0 : PCP over one letter (that is, all strings are from 1
∗) is decidable, because we work with numbers instead of

strings. If PCP over one letter is decidable, and we can always encode any number of letters into a single
letter (e.g., a = 1, b = 11, c = 111, d = 1111, etc.), explain how is it possible that PCP over an arbitrary
alphabet is undecidable?

V1 : Explain what is wrong with the following proof that PCP is decidable. Denote the top and bottom
strings by (x1, x2, . . . , xn) and (y1, y2, . . . , yn), resp. Considering all possible subsets of all possible per-
mutations of these blocks, we obtain 2n! possibilities. If we denote the maximum length of a string by
m = maxi=1..n(max(|xi|, |yi|)), this means the shortest solution, if any, must be of length at most m2n!.
The PCP is then decided by checking all potential solutions up to this length.

V2 : Show that the following restricted version of PCP is decidable: PCPr = {((x1, x2, . . . , xn), (y1, y2, . . . , yn)) |
n ≥ 1, xi, yi ∈ {a, b}+,max(|xi|, |yi|) ≤ 4, for all 1 ≤ i ≤ n}.

V3 : Given a positive number n, construct a PCP problem over {a, b} whose shortest solution has n blocks.
Explain why your answer is correct.