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 = {
V1 : L = {
V2 : L = {
V3 : L = {
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 = {
(b) L2 = {
(c) L3 = a
∗
V1 : (a) L1 = {
(b) L2 = {
(c) L3 = {ε}
V2 : (a) L1 = {
(b) L2 = {
(c) L3 = ∅
V3 : (a) L1 = {
(b) L2 = {
(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.