Last name (please print)
First name (please print)
Student Number
western university
department of computer science
CS3331 – Foundations of Computer Science – Fall 2015 – Final Exam
Instructor: Dr. Lucian Ilie
Friday, Dec. 11, 2015, 7:00pm – 10:00pm
P&AB106 (Absi – Meht), P&AB148 (Meye – Zhu)
This exam consists of 6 questions worth a total of 100 marks. No other materials are allowed, such as
cheat-sheets (or any other sheets), books, or electronic devices. All answers are to be written in this booklet.
For each question, if use the back of the page or the scrap work sheets at the end to write your answers, please indicate
this clearly on the page that contains the question. The exam is 120 minutes long and comprises 30% of your final
mark.
(1) 10pt
(2) 10pt
(3) 30pt
(4) 10pt
(5) 30pt
(6) 10pt
Grade
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 2
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 3
1. (10pt) Construct a deterministic Turing machine M that decides the language
L = {w ∈ {a, b}∗ | w contains at least three a’s} .
M starts with the initial configuration (s,�w) and halts with the configuration (q,�w), in the appropriate state
q ∈ {y, n}. Describe M using the macro language (e.g.: aR�bL#)
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 4
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 5
2. (10pt) The set SD is closed under intersection. Is the following a correct proof of this fact? Explain your answer.
Assume L1, L2 ∈ SD, semidecided by two Turing machines M1 and M2, respectively. We can build a
machine M to decide L1 ∩ L2 as follows:
1. on input w
2. run M1 on w
3. if M1 accepts, then
4. run M2 on w
5. if M2 accepts, then accept
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 6
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 7
3. (30pt) Can you give an example of a language L such that:
(a) L ∈ D and ¬L ∈ SD − D?
(b) L,¬L ∈ SD − D?
(c) L ∈ SD, ¬L 6∈ SD?
(d) L,¬L 6∈ SD?
Prove your answers. (¬L is the complement of L.)
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 8
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 9
4. (10pt) Assume a language L and a Turing machine M that lexicographically enumerates L. Construct a Turing
machine M ′ that decides ¬LR (the complement of the reversal of L). (Only clear English description is required.)
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 10
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 11
5. (30pt) For each of the following languages, prove 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 rigurously.
(a) L1 = {< M >| L(M) is finite}.
(b) L2 = {< M >| L(M) 6= ∅}.
(c) L3 = {< M1,M2 >| L(M1)− L(M2) is infinite}.
(d) L4 = {< M,w >|M accepts w and rejects wR}.
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 12
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 13
6. (10pt)
(a) Does the following instance of PCP have any solutions? Prove your answer.
a
bab
bbb
bb
aab
ab
b
a
(b) If you can determine, as you did at (a), whether a PCP instance has solutions or not, how is it possible
that the Post Correspondence Problem is undecidable?
(c) Can you give an example of an instance of PCP that has only one solution? Prove your answer.
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 14
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 15
(scrap work)
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 16
(scrap work)
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 17
(scrap work)
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 18
(scrap work)
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 19
(scrap work)
CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm – 10:00pm, P&AB106/148 20
(scrap work)